Cod sursa(job #3143845)

Utilizator emazareMazare Emanuel emazare Data 2 august 2023 15:35:01
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

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

int dx[8] = {-1,-1,0,1,1,1,0,-1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};

struct element{
    int x;
    int y;
    int dir;
};
const int Nmax = 505, INF = INT_MAX;
bool v[Nmax][Nmax];
int cost[Nmax][Nmax][8];
int n,m;
queue<element> q[2];

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

int main()
{
    int i,j,d,x1,y1,x2,y2,cmin;
    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];
            for(d=0;d<8;d++)
                cost[i][j][d] = INF;
        }
    }
    el.x = x1; el.y = y1;
    for(d=0;d<8;d++){
        cost[x1][y1][d] = 0;
        el.dir = d;
        q[0].push(el);
    }
    i = 0;
    while(!q[0].empty() || !q[1].empty()){
        j = (i+1)%2;
        el = q[i].front();
        el1.dir = el.dir;
        el1.x = el.x+dx[el.dir];
        el1.y = el.y+dy[el.dir];
        if(check(el1.x, el1.y) && cost[el1.x][el1.y][el1.dir] == INF){
            q[i].push(el1);
            cost[el1.x][el1.y][el1.dir] = cost[el.x][el.y][el.dir];
        }
        el1.x = el.x; el1.y = el.y; el1.dir = mod(el.dir - 1);
        if(cost[el1.x][el1.y][el1.dir] == INF){
            q[j].push(el1);
            cost[el1.x][el1.y][el1.dir] = cost[el.x][el.y][el.dir]+1;
        }
        el1.dir = mod(el.dir + 1);
        if(cost[el1.x][el1.y][el1.dir] == INF){
            q[j].push(el1);
            cost[el1.x][el1.y][el1.dir] = cost[el.x][el.y][el.dir]+1;
        }
        q[i].pop();
        if(q[i].empty())
            i = j;
    }
    cmin = INF;
    for(d=0;d<8;d++)
        cmin = min(cmin, cost[x2][y2][d]);
    if(cmin == INF)
        fout << "-1";
    else
        fout << cmin;
    return 0;
}