Pagini recente » Cod sursa (job #1432310) | Cod sursa (job #3264803)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMAX=501;
const int INF=2000000000;
int dx[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dy[8]={0, 1, 1, 1, 0, -1, -1, -1};
int n, m, xs, ys, xf, yf, a[NMAX][NMAX];
vector <vector <vector <int>>> dist;
deque <tuple <int,int,int>> dq;
void bordare(){
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;
}
}
void bfs(){
dist.assign(8, vector <vector <int>>(n+2, vector <int>(m+2, INF)));
int x, y, i, d, nx, ny, nd;
for(i=0;i<8;i++){
dq.push_back({i,xs,ys});
dist[i][xs][ys]=0;
}
while(!dq.empty()){
tie(d,x,y)=dq.front();
dq.pop_front();
nx=x+dx[d];
ny=y+dy[d];
if(!a[nx][ny]&&dist[d][nx][ny]>dist[d][x][y]){
dist[d][nx][ny]=dist[d][x][y];
dq.push_front({d,nx,ny});
}
for(int k=-1;k<=1;k+=2){
nd=(d+k+8)%8;
if(dist[d][x][y]+1<dist[nd][x][y]){
dist[nd][x][y]=dist[d][x][y]+1;
dq.push_back({nd,x,y});
}
}
}
}
int main(){
fin>>n>>m;
fin>>xs>>ys>>xf>>yf;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
fin>>a[i][j];
}
}
bordare();
bfs();
int ans=INF;
for(int i=0;i<8;i++){
if(dist[i][xf][yf]<ans)
ans=dist[i][xf][yf];
}
if(ans==INF) fout<<"-1";
else fout<<ans;
return 0;
}