Cod sursa(job #2824228)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 31 decembrie 2021 16:17:34
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int INF=1<<30;
struct nod{int x,y,d,o;};
struct cmp{bool operator()(nod const& a, nod const& b){return a.d>b.d;}};
priority_queue<nod,vector<nod>,cmp> q;
int n,m,i,j,sx,sy,fx,fy;
bool a[505][505],b[505][505][9];
int c[505][505][9];
bool in(int x, int y){return (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y]);}
int dist(int a, int b){return min(abs(a-b),8-abs(a-b));}
int main()
{
    fin>>n>>m>>sx>>sy>>fx>>fy;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            fin>>a[i][j];
            for(int k=1;k<9;k++)c[i][j][k]=INF;
        }
    for(i=1;i<9;i++)
    {
        b[sx][sy][i]=1;
        c[sx][sy][i]=0;
    }
    c[sx-1][sy-1][1]=0;
    c[sx-1][sy][2]=0;
    c[sx-1][sy+1][3]=0;
    c[sx][sy+1][4]=0;
    c[sx+1][sy+1][5]=0;
    c[sx+1][sy][6]=0;
    c[sx+1][sy-1][7]=0;
    c[sx][sy-1][8]=0;
    if(in(sx-1,sy-1))q.push({sx-1,sy-1,0,1});
    if(in(sx-1,sy))q.push({sx-1,sy,0,2});
    if(in(sx-1,sy+1))q.push({sx-1,sy+1,0,3});
    if(in(sx,sy+1))q.push({sx,sy+1,0,4});
    if(in(sx+1,sy+1))q.push({sx+1,sy+1,0,5});
    if(in(sx+1,sy))q.push({sx+1,sy,0,6});
    if(in(sx+1,sy-1))q.push({sx+1,sy-1,0,7});
    if(in(sx,sy-1))q.push({sx,sy-1,0,8});
    while(!q.empty())
    {
        nod top=q.top();
        q.pop();
        int x=top.x;
        int y=top.y;
        int d=top.d;
        int o=top.o;
        if(b[x][y][o])continue;
        b[x][y][o]=1;
        //b[x][y]=1;
        if(in(x-1,y-1)&&!b[x-1][y-1][1]&&c[x][y][o]+dist(o,1)<c[x-1][y-1][1]){q.push({x-1,y-1,c[x][y][o]+dist(o,1),1});c[x-1][y-1][1]=c[x][y][o]+dist(o,1);}
        if(in(x-1,y)&&!b[x-1][y][2]&&c[x][y][o]+dist(o,2)<c[x-1][y][2]){q.push({x-1,y,c[x][y][o]+dist(o,2),2});c[x-1][y][2]=c[x][y][o]+dist(o,2);}
        if(in(x-1,y+1)&&!b[x-1][y+1][3]&&c[x][y][o]+dist(o,3)<c[x-1][y+1][3]){q.push({x-1,y+1,c[x][y][o]+dist(o,3),3});c[x-1][y+1][3]=c[x][y][o]+dist(o,3);}
        if(in(x,y+1)&&!b[x][y+1][4]&&c[x][y][o]+dist(o,4)<c[x][y+1][4]){q.push({x,y+1,c[x][y][o]+dist(o,4),4});c[x][y+1][4]=c[x][y][o]+dist(o,4);}
        if(in(x+1,y+1)&&!b[x+1][y+1][5]&&c[x][y][o]+dist(o,5)<c[x+1][y+1][5]){q.push({x+1,y+1,c[x][y][o]+dist(o,5),5});c[x+1][y+1][5]=c[x][y][o]+dist(o,5);}
        if(in(x+1,y)&&!b[x+1][y][6]&&c[x][y][o]+dist(o,6)<c[x+1][y][6]){q.push({x+1,y,c[x][y][o]+dist(o,6),6});c[x+1][y][6]=c[x][y][o]+dist(o,6);}
        if(in(x+1,y-1)&&!b[x+1][y-1][7]&&c[x][y][o]+dist(o,7)<c[x+1][y-1][7]){q.push({x+1,y-1,c[x][y][o]+dist(o,7),7});c[x+1][y-1][7]=c[x][y][o]+dist(o,7);}
        if(in(x,y-1)&&!b[x][y-1][8]&&c[x][y][o]+dist(o,8)<c[x][y-1][8]){q.push({x,y-1,c[x][y][o]+dist(o,8),8});c[x][y-1][8]=c[x][y][o]+dist(o,8);}
        //if(in(x+1,y-1))cout<<"YAYYA   "<<c[x+1][y-1]<<'\n';;
    }
    int min1=INF;
    for(i=1;i<9;i++)
        min1=min(min1,c[fx][fy][i]);
    if(min1<INF)fout<<min1;
    else fout<<-1;
    return 0;
}