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