Cod sursa(job #2404643)

Utilizator bogdi1bogdan bancuta bogdi1 Data 13 aprilie 2019 11:01:15
Problema Car Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
struct Coord
{
    int x,y,dir,cost;
};
struct Costuri
{
    queue<Coord> q;
} v[5];
bool mat[505][505];
int sol[505][505][8];
int dlin[]={-1, -1, -1, 0, 1, 1, 1, 0};
int dcol[]={-1, 0, 1, 1, 1, 0, -1, -1};
bool viz[505][505][8];
int main()
{   freopen("car.in", "r",stdin);
    freopen("car.out", "w",stdout);
    int n,m,sx,sy,fx,fy,i,j,ok,mult=-1,k,minn=2000000000;
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &sx, &sy, &fx, &fy);
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            scanf("%d", &mat[i][j]);
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            for(k=0; k<8; k++)
                sol[i][j][k]=2000000000;
    for(i=0; i<=n+1; i++)
        mat[i][0]=mat[i][m+1]=1;
    for(i=0; i<=m+1; i++)
        mat[0][i]=mat[n+1][i]=1;
    for(i=0; i<8; i++){
        v[0].q.push({sx, sy, i, 0});
        sol[sx][sy][i]=0;
    }
    do{
            ok=0;
            for(i=0; i<=4; i++){
                while(!v[i].q.empty()){
                    ok=1;
                    Coord u=v[i].q.front();
                    if(viz[u.x][u.y][u.dir]==0){
                        viz[u.x][u.y][u.dir]=1;
                        for(k=0,j=u.dir; k<=4; j=(j+1)%8,k++)
                            if(mat[u.x+dlin[j]][u.y+dcol[j]]==0 && viz[u.x+dlin[j]][u.y+dcol[j]][j]==0 && sol[u.x+dlin[j]][u.y+dcol[j]][j]>u.cost+k){
                                v[(k+i)%5].q.push({u.x+dlin[j], u.y+dcol[j], j, u.cost+k});
                                sol[u.x+dlin[j]][u.y+dcol[j]][j]=u.cost+k;
                            }
                        for(k=1, j=(u.dir-1)+8*(u.dir==0); k<=3; k++,j=(j-1)+8*(j==0))
                            if(mat[u.x+dlin[j]][u.y+dcol[j]]==0 && viz[u.x+dlin[j]][u.y+dcol[j]][j]==0 && sol[u.x+dlin[j]][u.y+dcol[j]][j]>u.cost+k){
                                v[(k+i)%5].q.push({u.x+dlin[j], u.y+dcol[j], j, u.cost+k});
                                sol[u.x+dlin[j]][u.y+dcol[j]][j]=u.cost+k;
                            }
                    }
                    v[i].q.pop();
                }
            }
    }while(ok==1);
    for(i=0; i<8; i++)
        minn=min(minn, sol[fx][fy][i]);
    if(minn==2000000000)
        minn=-1;
    printf("%d", minn);
    return 0;
}