Cod sursa(job #2359335)

Utilizator DavidDragulinDragulin David DavidDragulin Data 28 februarie 2019 19:43:53
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>

using namespace std;

#define inf INT_MAX
#define mp make_pair
#define f first
#define s second

ifstream fin("car.in");
ofstream fout("car.out");
const int N=509;
int vx[]= {-1,-1,0,1,1,1,0,-1},vy[]= {0,1,1,1,0,-1,-1,-1},a[N][N],d[N][N];
int n,m,xi,yi,xf,yf,i,j;
queue <pair<int,pair<int,int> > > q;
void bordare()
{
    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;
}
void read()
{
    fin>>n>>m;
    fin>>xi>>yi>>xf>>yf;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            fin>>a[i][j];
}
void solve()
{
    int dir0[]= {0,1,2,3,4,3,2,1};
    int dir1[]= {1,0,1,2,3,4,3,2};
    int dir2[]= {2,1,0,1,2,3,4,3};
    int dir3[]= {3,2,1,0,1,2,3,4};
    int dir4[]= {4,3,2,1,0,1,2,3};
    int dir5[]= {3,4,3,2,1,0,1,2};
    int dir6[]= {2,3,4,3,2,1,0,1};
    int dir7[]= {1,2,3,4,3,2,1,0};
    bordare();
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            d[i][j]=inf;
    for(int i=0; i<8; i++)
        if(!a[xi+vx[i]][yi+vy[i]])
            q.push(mp(i,mp(xi+vx[i],yi+vy[i]))),d[xi+vx[i]][yi+vy[i]]=0;
    while(!q.empty())
    {
        int dir=q.front().f;
        int x=q.front().s.f;
        int y=q.front().s.s;
        q.pop();
        for(int i=0; i<8; i++)
        {
            if(a[x+vx[i]][y+vy[i]])
                continue;
            int dist;
            if(dir==0)
                dist=dir0[i];
            if(dir==1)
                dist=dir1[i];
            if(dir==2)
                dist=dir2[i];
            if(dir==3)
                dist=dir3[i];
            if(dir==4)
                dist=dir4[i];
            if(dir==5)
                dist=dir5[i];
            if(dir==6)
                dist=dir6[i];
            if(dir==7)
                dist=dir7[i];
            if(d[x+vx[i]][y+vy[i]]>d[x][y]+dist)
            {
                d[x+vx[i]][y+vy[i]]=d[x][y]+dist;
                q.push(mp(i,mp(x+vx[i],y+vy[i])));
            }
        }
    }
    fout<<(d[xf][yf]==inf? -1 :d[xf][yf]);
}
int main()
{
    read();
    solve();
    return 0;
}