Cod sursa(job #3276628)

Utilizator tudor_costinCostin Tudor tudor_costin Data 13 februarie 2025 22:20:09
Problema Car Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int dx[]= {-1,-1,0,1,1,1,0,-1};
const int dy[]= {0,1,1,1,0,-1,-1,-1};
const int Nmax=505;
bool a[Nmax][Nmax];
bool viz[Nmax][Nmax][10];
int d[Nmax][Nmax][10];
bool inq[Nmax][Nmax][10];
struct celula
{
    short int x,y;
    short int dir;
};
int n,m;
bool inmat(int i,int j)
{
    return (1<=i && i<=n && 1<=j && j<=m);
}
int main()
{
    fin>>n>>m;
    int sx,sy,fx,fy;
    fin>>sx>>sy>>fx>>fy;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            fin>>a[i][j];
            for(int k=0;k<8;k++) d[i][j][k]=-1;
        }
    }
    queue<celula> q;
    for(int k=0;k<8;k++)
    {
        q.push({sx,sy,k});
        d[sx][sy][k]=0;
    }
    while(!q.empty())
    {
        int i=q.front().x;
        int j=q.front().y;
        int dr=q.front().dir;
        int cost=d[i][j][dr];
        q.pop();
        inq[i][j][dr]=0;
        int newi=i+dx[dr],newj=j+dy[dr];
        if(inmat(newi,newj) && a[i][j]!=1)
        {
            if(d[newi][newj][dr]==-1 || d[newi][newj][dr]>cost)
            {
                d[newi][newj][dr]=cost;
                if(!inq[newi][newj][dr])
                {
                    q.push({newi,newj,dr});
                    inq[newi][newj][dr]=1;
                }
            }
        }
        for(int turn=1;turn<=4;turn++)
        {
            int k=(dr+turn)%8;
            if(d[i][j][k]==-1 || d[i][j][k]>cost+turn)
            {
                d[i][j][k]=cost+turn;
                if(!inq[i][j][k])
                {
                    q.push({i,j,k});
                    inq[i][j][k]=1;
                }
            }
            if(turn==4) continue;
            k=(dr+8-turn)%8;
            if(d[i][j][k]==-1 || d[i][j][k]>cost+turn)
            {
                d[i][j][k]=cost+turn;
                if(!inq[i][j][k])
                {
                    q.push({i,j,k});
                    inq[i][j][k]=1;
                }
            }
        }
    }
    int ans=INT_MAX;
    for(int k=0;k<8;k++) if(d[fx][fy][k]!=-1) ans=min(ans,d[fx][fy][k]);
    fout<<ans<<'\n';
    return 0;
}