Pagini recente » Cod sursa (job #1684191) | Cod sursa (job #280096) | Cod sursa (job #1488653) | Cod sursa (job #2256380) | Cod sursa (job #2030048)
#include <bits/stdc++.h>
using namespace std;
const int maxN=505;
const int INF=0x3f3f3f3f;
const int dx[]={-1,-1,-1,0,1,1,1,0};
const int dy[]={-1,0,1,1,1,0,-1,-1};
int a[maxN][maxN];
int dist[maxN][maxN][8];
int n,m,xst,yst,xfn,yfn;
deque<pair<pair<int,int>,int> >deq;
int main()
{
ifstream f("car.in");
ofstream g("car.out");
f>>n>>m;
f>>xst>>yst>>xfn>>yfn;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f>>a[i][j];
memset(dist,INF,sizeof(dist));
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;
for(int i=0;i<8;i++){
dist[xst][yst][i]=0;
deq.push_front({{xst,yst},i});
}
while(!deq.empty())
{
int x=deq.front().first.first;
int y=deq.front().first.second;
int dir=deq.front().second;
deq.pop_front();
if(x==xfn && y==yfn){
g<<dist[x][y][dir];
return 0;
}
int newdir=(dir+7)%8;
if(!a[x][y] && dist[x][y][newdir]>dist[x][y][dir]+1){
dist[x][y][newdir]=dist[x][y][dir]+1;
deq.push_back({{x,y},newdir});
}
newdir=(dir+1)%8;
if(!a[x][y] && dist[x][y][newdir]>dist[x][y][dir]+1){
dist[x][y][newdir]=dist[x][y][dir]+1;
deq.push_back({{x,y},newdir});
}
newdir=dir;
if(!a[x+dx[dir]][y+dy[dir]] && dist[x+dx[dir]][y+dy[dir]][newdir]>dist[x][y][dir]){
dist[x+dx[dir]][y+dy[dir]][newdir]=dist[x][y][dir];
deq.push_front({{x+dx[dir],y+dy[dir]},newdir});
}
}
g<<-1;
return 0;
}