Cod sursa(job #3191831)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 10 ianuarie 2024 19:02:38
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

ifstream fin ("car.in");
ofstream fout ("car.out");

const int NMAX=5e2+5;
const int INF=2e9;

int di[]={1,1,1,0,-1,-1,-1,0};
int dj[]={1,0,-1,-1,-1,0,1,1};

struct elem{
    int x;
    int y;
    int c;
    int d;
};

int dp[NMAX][NMAX][10];
bool a[NMAX][NMAX];
queue<elem>q[2];
int n,m;

bool intmat(int i,int j)
{
    return 1<=i && 1<=j && i<=n && j<=m;
}

void bfs(int x1,int y1)
{
    int i,j,dir;
    for(dir=0;dir<8;dir++)
        q[0].push({x1,y1,0,dir});
    while(!q[0].empty())
    {
        while(!q[0].empty())
        {
            elem p=q[0].front();
            q[0].pop();
            elem aux;
            aux.x=p.x+di[p.d];
            aux.y=p.y+dj[p.d];
            aux.c=p.c;
            aux.d=p.d;
            if(intmat(aux.x,aux.y) && a[aux.x][aux.y]==0 && dp[aux.x][aux.y][aux.d]>aux.c)
            {
                dp[aux.x][aux.y][aux.d]=aux.c;
                q[0].push(aux);
            }
            aux.x=p.x;
            aux.y=p.y;
            aux.c=p.c+1;
            aux.d=(p.d+1)%8;
            if(intmat(aux.x,aux.y) && a[aux.x][aux.y]==0 && dp[aux.x][aux.y][aux.d]>aux.c)
            {
                dp[aux.x][aux.y][aux.d]=aux.c;
                q[1].push(aux);
            }
            aux.d=(p.d+7)%8;
            if(intmat(aux.x,aux.y) && a[aux.x][aux.y]==0 && dp[aux.x][aux.y][aux.d]>aux.c)
            {
                dp[aux.x][aux.y][aux.d]=aux.c;
                q[1].push(aux);
            }
        }
        while(!q[1].empty())
        {
            elem p=q[1].front();
            q[0].push(p);
            q[1].pop();
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int x1,x2,y1,y2,i,j,dir,best=INF;
    fin>>n>>m>>x1>>y1>>x2>>y2;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            fin>>a[i][j];
            for(dir=0;dir<8;dir++)
                dp[i][j][dir]=INF;
        }
    }
    bfs(x1,y1);
    for(dir=0;dir<8;dir++)
        best=min(best,dp[x2][y2][dir]);
    if(best==INF)
        fout<<-1;
    else
        fout<<best;
    return 0;
}