Cod sursa(job #2030046)

Utilizator LucianTLucian Trepteanu LucianT Data 30 septembrie 2017 23:16:04
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>
using namespace std;
const int maxN=505;
const int INF=0x3f3f3f3f;

const int dx[]={-1,-1,-1,0,1,1,1,0};
const int dy[]={-1,0,1,1,1,0,-1,-1};

int a[maxN][maxN];
int dist[maxN][maxN][8];
int n,m,xst,yst,xfn,yfn;
deque<pair<pair<int,int>,int> >deq;

int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);

    scanf("%d %d",&n,&m);
    scanf("%d %d %d %d",&xst,&yst,&xfn,&yfn);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);

    memset(dist,INF,sizeof(dist));

    for(int i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]=1;

    for(int i=0;i<=m+1;i++)
        a[0][i]=a[n+1][i]=1;

    for(int i=0;i<8;i++){
        dist[xst][yst][i]=0;
        deq.push_front({{xst,yst},i});
    }

    while(!deq.empty())
    {
        cerr<<"ICI ";
        int x=deq.front().first.first;
        int y=deq.front().first.second;
        int dir=deq.front().second;
        deq.pop_front();

        if(x==xfn && y==yfn){
            printf("%d",dist[x][y][dir]);
            return 0;
        }

        int newdir=(dir+7)%8;
        if(!a[x][y] && dist[x][y][newdir]>dist[x][y][dir]+1){
            dist[x][y][newdir]=dist[x][y][dir]+1;
            deq.push_back({{x,y},newdir});
        }

        newdir=(dir+1)%8;
        if(!a[x][y] && dist[x][y][newdir]>dist[x][y][dir]+1){
            dist[x][y][newdir]=dist[x][y][dir]+1;
            deq.push_back({{x,y},newdir});
        }

        newdir=dir;
        if(!a[x+dx[dir]][y+dy[dir]] && dist[x+dx[dir]][y+dy[dir]][newdir]>dist[x][y][dir]){
            dist[x+dx[dir]][y+dy[dir]][newdir]=dist[x][y][dir];
            deq.push_front({{x+dx[dir],y+dy[dir]},newdir});
        }
    }

    printf("-1");

    return 0;
}