Cod sursa(job #3305890)

Utilizator vlad7654vladimir manescu vlad7654 Data 5 august 2025 23:12:20
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMAX=500, directions=8, inf=1e9;
const int dx[]={-1,-1,-1,0,1,1,1,0};
const int dy[]={-1,0,1,1,1,0,-1,-1};
vector<vector<vector<int> > > dist;
deque<tuple<int,int,int> > dq;
vector<vector<int> > mat(NMAX+5, vector<int>(NMAX+5, 0));
int n, m, xs, ys, xf, yf;
bool check(int i,int j){
    if(i>=1 and i<=n and j>=1 and j<=m){
        return true;
    }
    return false;
}
void bfs01(){
    dist.assign(directions,vector<vector<int>>(n+1, vector<int>(m+1,inf)));
    for(int i=0;i<directions;i++){
        dist[i][xs][ys]=0;
        dq.push_back({i,xs,ys});
    }
    while(!dq.empty()){
        int x, y, direction, nx, ny, ndirection;
        tie(direction,x,y)=dq.front();
        dq.pop_front();
        nx=x+dx[direction];
        ny=y+dy[direction];
        if(check(nx, ny) and mat[nx][ny]==0 and dist[direction][nx][ny]>dist[direction][x][y]){
            dist[direction][nx][ny]=dist[direction][x][y];
            dq.push_front({direction,nx,ny});
        }
        for(int k=-1;k<=1;k+=2){
            ndirection=(direction+k+directions)%directions;
            if(dist[direction][x][y]+1<dist[ndirection][x][y]){
                dist[ndirection][x][y]=dist[direction][x][y]+1;
                dq.push_front({ndirection,x,y});
            }
        }
    }
}
int main(){
    fin>>n>>m>>xs>>ys>>xf>>yf;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fin>>mat[i][j];
        }
    }
    bfs01();
    int ans=inf;
    for(int i=0;i<directions;i++){
        if(ans>dist[i][xf][yf]){
            ans=dist[i][xf][yf];
        }
    }
    if(ans==inf){
        fout<<-1;
    }else{
        fout<<ans;
    }

}