Cod sursa(job #2634931)

Utilizator loraclorac lorac lorac Data 12 iulie 2020 18:58:28
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
#define Op pair<int,pair<int,int> >
priority_queue<Op,vector<Op>,greater<Op> > pq;
const int inf=2e9+7;
int n,m,xx0,yy0,xx1,yy1,ans=inf;
bool ok[505][505];
int dist[9][505][505];
int diff[9][9];
const int dx[]={-1, 0, 1,1,1,0,-1,-1};
const int dy[]={-1,-1,-1,0,1,1, 1, 0};
bool interior(int xx,int yy)
{
    if(0<=xx and xx<n and 0<=yy and yy<m and !ok[xx][yy])
        return true;
    return false;
}
void init()
{
    for(int i=0;i<8;++i)
    for(int j=0;j<8;++j)
        diff[i][j]=min(abs(i-j),8-abs(i-j));
}
void dijkstra()
{
    for(int k=0;k<8;++k)
    for(int i=0;i<n;++i)
    for(int j=0;j<m;++j)
        dist[k][i][j]=inf;
    for(int k=0;k<8;++k)
    {
        dist[k][xx0][yy0]=0;
        pq.push({0,{xx0*m+yy0,k}});
    }
    while(!pq.empty())
    {
        int ct=pq.top().first;
        int nr=(pq.top().second).first;
        int dir=(pq.top().second).second;
        pq.pop();
        int x=nr/m,y=nr%m;
        if(dist[dir][x][y]!=ct) continue;
        if(x==xx1 and y==yy1) {ans=min(ans,ct);continue;}
        for(int d=0;d<8;++d)
        {
            int xx=x+dx[d];
            int yy=y+dy[d];
            if(interior(xx,yy) and dist[d][xx][yy]>ct+diff[dir][d])
            {
                dist[d][xx][yy]=ct+diff[dir][d];
                pq.push({dist[d][xx][yy],{xx*m+yy,d}});
            }
        }
    }
}
int main()
{
    in>>n>>m>>xx0>>yy0>>xx1>>yy1;
    --xx0;--yy0;--xx1;--yy1;
    for(int i=0;i<n;++i)
    for(int j=0;j<m;++j)
        in>>ok[i][j];
    init();
    dijkstra();
    out<<ans<<'\n';
    return 0;
}