Pagini recente » Cod sursa (job #3258550) | Cod sursa (job #3255605) | Cod sursa (job #322004) | Cod sursa (job #3129167) | Cod sursa (job #3143050)
#include <fstream>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int Nmax = 505, INF = INT_MAX;
int dx[8] = {-1,-1,0,1,1,1,0,-1}, dy[8] = {0,1,1,1,0,-1,-1,-1};
bool v[Nmax][Nmax],used[Nmax][Nmax][10];
struct element{
int x;
int y;
int d;
int c;
};
int L[Nmax][Nmax];
queue<element> q[2];
int n,m;
bool check(int a, int b){
if(a>0 && a<=n && b>0 && b<=m && !v[a][b])
return 1;
return 0;
}
int mod(int a){
if(a == -1)
return 7;
if(a == 8)
return 0;
return a;
}
int main()
{
int i,j,d,x1,y1,x2,y2;
element el,el1;
fin >> n >> m;
fin >> x1 >> y1 >> x2 >> y2;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
fin >> v[i][j];
L[i][j] = INF;
}
}
el.x = x1; el.y = y1; el.c = 0;
for(d=0;d<8;d++){
el.d = d;
q[0].push(el);
used[x1][y1][d] = 1;
}
L[x1][y1] = 0;
i = 0;
while(!q[0].empty() || !q[1].empty()){
el = q[i].front();
el1.x = el.x+dx[el.d];
el1.y = el.y+dy[el.d];
el1.c = el.c;
el1.d = el.d;
if(check(el1.x, el1.y) && !used[el1.x][el1.y][el1.d]){
q[i].push(el1);
if(L[el1.x][el1.y]>el1.c)
L[el1.x][el1.y] = el1.c;
used[el1.x][el1.y][el1.d] = 1;
}
el1.x = el.x; el1.y = el.y; el1.c = el.c+1; el1.d = mod(el.d-1);
if(!used[el1.x][el1.y][el1.d]){
q[(i+1)%2].push(el1);
used[el1.x][el1.y][el1.d] = 1;
}
el1.d = mod(el.d+1);
if(!used[el1.x][el1.y][el1.d]){
q[(i+1)%2].push(el1);
used[el1.x][el1.y][el1.d] = 1;
}
q[i].pop();
if(q[i].empty())
i = (i+1)%2;
}
if(L[x2][y2] == INF)
fout << "-1";
else
fout << L[x2][y2];
return 0;
}