Cod sursa(job #3264805)

Utilizator mariusharabariMarius Harabari mariusharabari Data 24 decembrie 2024 10:45:49
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX=505;
const int INF=2000000000;
int dx[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dy[8]={0, 1, 1, 1, 0, -1, -1, -1};

int n, m, xs, ys, xf, yf, a[NMAX][NMAX];
vector <vector <vector <int>>> dist;
deque <tuple <int,int,int>> dq;

void bordare(){
    for(int i=0;i<=n+1;i++){
        a[i][0]=a[i][m+1]=1;
    }
    for(int i=0;i<=m+1;i++){
        a[0][i]=a[n+1][i]=1;
    }
}

void bfs(){
    dist.assign(8, vector <vector <int>>(n+2, vector <int>(m+2, INF)));
    int x, y, i, d, nx, ny, nd;
    for(i=0;i<8;i++){
        dq.push_back({i,xs,ys});
        dist[i][xs][ys]=0;
    }
    while(!dq.empty()){
        tie(d,x,y)=dq.front();
        dq.pop_front();

        nx=x+dx[d];
        ny=y+dy[d];
        if(!a[nx][ny]&&dist[d][nx][ny]>dist[d][x][y]){
            dist[d][nx][ny]=dist[d][x][y];
            dq.push_front({d,nx,ny});
        }
        for(int k=-1;k<=1;k+=2){
            nd=(d+k+8)%8;
            if(dist[d][x][y]+1<dist[nd][x][y]){
                dist[nd][x][y]=dist[d][x][y]+1;
                dq.push_back({nd,x,y});
            }
        }
    }
}

int main(){
    fin>>n>>m;
    fin>>xs>>ys>>xf>>yf;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fin>>a[i][j];
        }
    }
    bordare();

    bfs();

    int ans=INF;
    for(int i=0;i<8;i++){
        if(dist[i][xf][yf]<ans)
            ans=dist[i][xf][yf];
    }
    if(ans==INF) fout<<"-1";
    else fout<<ans;
    return 0;
}