Cod sursa(job #3142811)

Utilizator emazareMazare Emanuel emazare Data 24 iulie 2023 17:15:34
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

const int Nmax = 505, INF = INT_MAX;
int dx[8] = {-1,-1,0,1,1,1,0,-1}, dy[8] = {0,1,1,1,0,-1,-1,-1};
bool v[Nmax][Nmax],used[Nmax][Nmax][10];
struct element{
    int x;
    int y;
    int d;
    int c;
};
int L[Nmax][Nmax];
queue<element> q[2];
int n,m;

bool check(int a, int b){
    if(a>0 && a<=n && b>0 && b<=m && !v[a][b])
        return 1;
    return 0;
}

int mod(int a){
    if(a == -1)
        return 7;
    if(a == 8)
        return 0;
    return a;
}

int main()
{
    int i,j,d,x1,y1,x2,y2;
    element el,el1;
    fin >> n >> m;
    fin >> x1 >> y1 >> x2 >> y2;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            fin >> v[i][j];
            L[i][j] = INF;
        }
    }
    el.x = x1; el.y = y1; el.c = 0;
    for(d=0;d<8;d++){
        el.d = d;
        q[0].push(el);
        used[x1][y1][d] = 1;
    }
    L[x1][y1] = 0;
    i = 0;
    while(!q[0].empty() || !q[1].empty()){
        el = q[i].front();
        el1.x = el.x+dx[el.d];
        el1.y = el.y+dy[el.d];
        el1.c = el.c;
        el1.d = el.d;
        if(check(el1.x, el1.y) && !used[el1.x][el1.y][el1.d]){
            q[i].push(el1);
            if(L[el1.x][el1.y]>el1.c)
                L[el1.x][el1.y] = el1.c;
            used[el1.x][el1.y][el1.d] = 1;
        }
        el1.x = el.x; el1.y = el.y; el1.c = el.c+1; el1.d = mod(el.d-1);
        if(!used[el1.x][el1.y][el1.d]){
            q[(i+1)%2].push(el1);
            used[el1.x][el1.y][el1.d] = 1;
        }
        el1.d = mod(el.d+1);
        if(!used[el1.x][el1.y][el1.d]){
            q[(i+1)%2].push(el1);
            used[el1.x][el1.y][el1.d] = 1;
        }
        q[i].pop();
        if(q[i].empty())
            i = (i+1)%2;
    }
    if(L[x2][y2] == INF)
        fout << "-1";
    else
        fout << L[x2][y2];
    return 0;
}