Cod sursa(job #3305943)

Utilizator vlad7654vladimir manescu vlad7654 Data 6 august 2025 09:50:16
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMAX=500, directions=8, inf=1e12;
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(8, vector<vector<int>>(NMAX+5,vector<int>(NMAX+5,inf)));
queue<tuple<int,int,int> > q[3];
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 dial(){
    int total_elements=directions, cur_q=0;
    for(int i=0;i<directions;i++){
        dist[i][xs][ys]=0;
        q[cur_q].push({i,xs,ys});
    }
    while(total_elements){
        while(q[cur_q].empty()){
            cur_q=(cur_q+1)%3;
        }
        int x, y, nx, ny, direction, ndirection;
        tie(direction, x, y)=q[cur_q].front();
        q[cur_q].pop(), total_elements--;
        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];
            q[cur_q].push({direction,nx,ny}), total_elements++;
        }
        for(int k=-2;k<0;k++){
            ndirection=(direction+k+directions)%directions;
            nx=x+dx[ndirection];
            ny=y+dy[ndirection];
            if(check(nx,ny) and mat[nx][ny]==0 and dist[ndirection][nx][ny]>dist[direction][x][y]-k){
                dist[ndirection][nx][ny]=dist[direction][x][y]-k;
                q[cur_q].push({ndirection,nx,ny}), total_elements++;
            }
        }
        for(int k=1;k<=2;k++){
            ndirection=(direction+k)%directions;
            nx=x+dx[ndirection];
            ny=y+dy[ndirection];
            if(check(nx,ny) and mat[nx][ny]==0 and dist[ndirection][nx][ny]>dist[direction][x][y]+k){
                dist[ndirection][nx][ny]=dist[direction][x][y]+k;
                q[cur_q].push({ndirection,nx,ny}), total_elements++;
            }
        }
    }
}
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++){
        if(ans>dist[i][xf][yf]){
            ans=dist[i][xf][yf];
        }
    }
    if(ans==inf){
        fout<<-1;
    }else{
        fout<<ans;
    }

}