Cod sursa(job #3307079)

Utilizator vlad7654vladimir manescu vlad7654 Data 16 august 2025 22:39:47
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMAX=500, directions=8, inf=1e9;
int mat[NMAX+5][NMAX+5];
vector<vector<vector<int>>> dist(directions, vector<vector<int> >(NMAX+5, vector<int>(NMAX+5, inf)));
int xs, ys, xf, yf;
const int dx[]={-1,-1,-1,0,1,1,1,0};
const int dy[]={-1,0,1,1,1,0,-1,-1};
int n, m;
bool inmat(int x, int y){
    return x>=1 and x<=n and y>=1 and y<=m;
}
void dial(){
    queue<tuple<int,int,int> > q[3];
    int cnt=directions, cur=0;
    for(int i=0;i<directions;i++){
        q[cur].push(tie(xs,ys,i));
        dist[i][xs][ys]=0;
    }
    while(cnt){
        while(q[cur].empty()){
            cur=(cur+1)%3;
        }
        int x, y, direction;
        tie(x, y, direction)=q[cur].front();
        q[cur].pop();
        cnt--;
        for(int k=-2;k<=2;k++){
            int nx, ny, ndirection;
            ndirection=(direction+k+directions)%directions;
            nx=x+dx[ndirection];
            ny=y+dy[ndirection];
            if(inmat(nx,ny) and mat[nx][ny]==0){
                if(dist[ndirection][nx][ny]>dist[direction][x][y]+abs(k)){
                    dist[ndirection][nx][ny]=dist[direction][x][y]+abs(k);
                    q[(cur+abs(k))%3].push({nx,ny,ndirection});
                    cnt++;
                }
            }
        }

    }
}

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];
        }
    }
    dial();
    int ans=inf;
    for(int i=0;i<directions;i++){
        ans=min(ans, dist[i][xf][yf]);
    }
    if(ans!=inf){
        fout<<ans;
    }else{
        fout<<-1;
    }
}