Cod sursa(job #3167681)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 10 noiembrie 2023 23:22:20
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
const int NMAX=505,INF=0x3F3F3F3F,DIRECTIONS=8;
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,xs,ys,xf,yf,ans;
bitset<NMAX>a[NMAX];
deque<tuple<int,int,int>>dq;
vector<vector<vector<int>>>d;
inline bool check(int i,int j)
{
    if(i>=1 && i<=n && j>=1 && j<=m)
        return 1;
    return 0;
}
void bfs01()
{
    int x,y,direction,nx,ny,ndirection;
    d.assign(DIRECTIONS,vector<vector<int>>(n+1,vector<int>(m+1,INF)));
    for(int i=0; i<DIRECTIONS; i++)
    {
        d[i][xs][ys]=0;
        dq.push_back({i,xs,ys});
    }
    while(!dq.empty())
    {
        tie(direction,x,y)=dq.front();
        dq.pop_front();
        nx=x+dx[direction];
        ny=y+dy[direction];
        if(check(nx,ny) && !a[nx][ny] && d[direction][x][y]<d[direction][nx][ny])///we check for 0 degrees - edge with cost 0 in BFS 0-1
        {
            d[direction][nx][ny]=d[direction][x][y];
            dq.push_front({direction,nx,ny});
        }
        for(int k=-1; k<=1; k+=2) ///we check for 45 degrees to the left and 45 degrees to the right - edge with cost 1 in BFS 0-1
        {
            ndirection=(direction+k+8)%DIRECTIONS;
            if(d[direction][x][y]+1<d[ndirection][x][y])
            {
                d[ndirection][x][y]=d[direction][x][y]+1;
                dq.push_back({ndirection,x,y});
            }
        }
    }
}
int main()
{
    f>>n>>m>>xs>>ys>>xf>>yf;
    for(int i=1,x; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            f>>x;
            a[i][j]=x;
        }
    bfs01();
    ans=INF;
    for(int i=0; i<DIRECTIONS; i++)
        if(d[i][xf][yf]<ans)
            ans=d[i][xf][yf];
    if(ans==INF)
        g<<-1;
    else
        g<<ans;
    return 0;
}