Pagini recente » Cod sursa (job #2114524) | Cod sursa (job #1886752) | Cod sursa (job #1154257) | Cod sursa (job #1839551) | Cod sursa (job #2436703)
#include <iostream>
#include <cstdio>
#include <queue>
#define inf 1000001
#define x first
#define y second
using namespace std;
int Ox[8]={-1, -1, 0, 1, 1, 1, 0, -1};
int Oy[8]={0, 1, 1, 1, 0, -1, -1, -1};
int N, M, i, j, k, area[501][501], solution[501][501][8];
pair<int, int> start, finish;
struct dot{
int x, y, d;
};
queue<dot> q, next_q;
int main(){
freopen("car.in", "r", stdin);
freopen("car.out", "w", stdout);
scanf("%d%d%d%d%d%d", &N, &M, &start.x, &start.y, &finish.x, &finish.y);
for(i=1; i<=N; ++i)
for(j=1; j<=M; ++j){
scanf("%d", &area[i][j]);
area[i][j]=1-area[i][j];
for(k=0; k<8; ++k) solution[i][j][k]=inf;
}
for(i=0; i<8; ++i){
solution[start.x][start.y][i]=1;
q.push({start.x, start.y, i});
}
while(!q.empty()){
while(!q.empty()){
dot pos=q.front(), nbr; q.pop();
if(pos.x==finish.x && pos.y==finish.y) {printf("%d", solution[pos.x][pos.y][pos.d]-1); return 0;}
nbr=pos; nbr.x+=Ox[nbr.d]; nbr.y+=Oy[nbr.d];
if(area[nbr.x][nbr.y]==1 && solution[pos.x][pos.y][pos.d]<solution[nbr.x][nbr.y][nbr.d]){
q.push(nbr);
solution[nbr.x][nbr.y][nbr.d]=solution[pos.x][pos.y][pos.d];
}
nbr=pos; nbr.d=(nbr.d+1)%8;
if(area[nbr.x][nbr.y]==1 && solution[pos.x][pos.y][pos.d]+1<solution[nbr.x][nbr.y][nbr.d]){
next_q.push(nbr);
solution[nbr.x][nbr.y][nbr.d]=solution[pos.x][pos.y][pos.d]+1;
}
nbr=pos; --nbr.d; if(nbr.d==-1) nbr.d=7;
if(area[nbr.x][nbr.y]==1 && solution[pos.x][pos.y][pos.d]+1<solution[nbr.x][nbr.y][nbr.d]){
next_q.push(nbr);
solution[nbr.x][nbr.y][nbr.d]=solution[pos.x][pos.y][pos.d]+1;
}
}
while(!next_q.empty()){
q.push(next_q.front());
next_q.pop();
}
}
printf("-1");
return 0;
}