Pagini recente » Cod sursa (job #1140146) | Cod sursa (job #1405114) | Cod sursa (job #865167) | Cod sursa (job #2348148) | Cod sursa (job #2634931)
#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;
}