Cod sursa(job #3251881)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 27 octombrie 2024 17:02:34
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3F3F3F3F;
const int Nmax = 501;
const int di[]= {-1,-1,-1,0,1,1,1,0};
const int dj[]= {-1,0,1,1,1,0,-1,-1};
int directie = 8;
int n, m, xs, ys, xf, yf, a[Nmax][Nmax], used[8][Nmax][Nmax];
vector<vector<vector<int>>> d;
queue<tuple<int, int, int>> q[3];
bool inmat(int i, int j)
{
    return i>=1 && i<=n && j>=1 && j<=m;
}
void iliubescpedial()
{

    for(int i=0; i<directie; i++)
    {
        d[i][xs][ys] = 0;
        q[0].push({i, xs, ys});
    }
    int qun = 0, cnt = directie;
    int dir = 0, x = 0, y = 0, xnou, ynou, dirnou;
    while(cnt > 0)
    {
        while(q[qun].empty())
            qun = (qun + 1) % 3;
        tie(dir, x, y) = q[qun].front();
        q[qun].pop();
        cnt--;
        if(!used[dir][x][y])
        {
            for(int k=-2; k<0; k++)
            {
                dirnou = (dir + k + 8) % directie;
                xnou = x + di[dirnou];
                ynou = y + dj[dirnou];
                if(inmat(xnou, ynou) && !a[xnou][ynou] && !used[dirnou][xnou][ynou] && d[dir][x][y] - k < d[dirnou][xnou][ynou])
                {
                    d[dirnou][xnou][ynou] = d[dir][x][y] - k;
                    q[(d[dir][x][y] - k) % 3].push({dirnou, xnou, ynou});
                    cnt++;
                }
            }
            for(int k=0; k<=2; k++)
            {
                dirnou = (dir + k) % 8;
                xnou = x + di[dirnou];
                ynou = y + dj[dirnou];
                if(inmat(xnou, ynou) && !a[xnou][ynou] && !used[dirnou][xnou][ynou] && d[dir][x][y] + k < d[dirnou][xnou][ynou])
                {
                    d[dirnou][xnou][ynou] = d[dir][x][y] + k;
                    q[(d[dir][x][y] + k) % 3].push({dirnou, xnou, ynou});
                    cnt++;
                }
            }
            used[dir][x][y] = 1;
        }
    }
}
int main()
{
    ifstream cin("car.in");
    ofstream cout("car.out");
    cin >> n >> m;
    d.assign(directie,vector<vector<int>>(n+1,vector<int>(m+1,INF)));
    cin >> xs >> ys >> xf >> yf;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> a[i][j];
    iliubescpedial();
    int ans = INF;
    for(int i=0; i<8; i++)
        ans = min(ans, d[i][xf][yf]);
    if(ans == INF)
        cout << "-1";
    else
        cout << ans;
    return 0;
}