Pagini recente » Cod sursa (job #1601779) | Cod sursa (job #2962455) | Cod sursa (job #2633353) | Cod sursa (job #2958882) | Cod sursa (job #1268254)
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 505;
struct Position {
int x, y, dir;
};
int a [N][N], c [8][N][N];
int dx [] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy [] = {-1, 0, 1, 1, 1, 0, -1, -1};
queue <Position> q [2];
int n, m;
Position S, F;
int main () {
int i, j, l, l1, l2, cost;
Position node, temp;
freopen ("car.in", "r", stdin);
freopen ("car.out", "w", stdout);
scanf ("%d%d%d%d%d%d", &n, &m, &S.x, &S.y, &F.x, &F.y);
for (i = 1; i <= n; i ++)
for (j = 1; j <= m; j ++)
scanf ("%d", &a [i][j]);
if (S.x == F.x && S.y == F.y) {
printf ("0\n");
return 0;
}
S.dir = 0;
q [0].push (S);
S.dir = 1;
q [0].push (S);
S.dir = 2;
q [0].push (S);
S.dir = 3;
q [0].push (S);
S.dir = 4;
q [0].push (S);
S.dir = 5;
q [0].push (S);
S.dir = 6;
q [0].push (S);
S.dir = 7;
q [0].push (S);
memset (c, -1, sizeof (c));
c [0][S.x][S.y] = 0;
c [1][S.x][S.y] = 0;
c [2][S.x][S.y] = 0;
c [3][S.x][S.y] = 0;
c [4][S.x][S.y] = 0;
c [5][S.x][S.y] = 0;
c [6][S.x][S.y] = 0;
c [7][S.x][S.y] = 0;
l = 0;
while (!q [l % 2].empty ()) {
l ++;
l1 = (l % 2);
l2 = ((l - 1) % 2);
while (!q [l2].empty ()) {
node = q [l2].front ();
q [l2].pop ();
temp.x = node.x + dx [node.dir];
temp.y = node.y + dy [node.dir];
temp.dir = node.dir;
if (temp.x >= 1 && temp.x <= n && temp.y >= 1 && temp.y <= m && a [temp.x][temp.y] == 0) {
if (c [temp.dir][temp.x][temp.y] == -1 || (c [temp.dir][temp.x][temp.y] != -1 && c [temp.dir][temp.x][temp.y] > c [node.dir][node.x][node.y])) {
q [l2].push (temp);
c [temp.dir][temp.x][temp.y] = c [node.dir][node.x][node.y];
if (temp.x == F.x && temp.y == F.y) {
printf ("%d\n", c [temp.dir][temp.x][temp.y]);
return 0;
}
}
}
temp.x = node.x;
temp.y = node.y;
temp.dir = node.dir + 1;
if (temp.dir == 8)
temp.dir = 0;
if (temp.x >= 1 && temp.x <= n && temp.y >= 1 && temp.y <= m && a [temp.x][temp.y] == 0) {
if (c [temp.dir][temp.x][temp.y] == -1 || (c [temp.dir][temp.x][temp.y] != -1 && c [temp.dir][temp.x][temp.y] > c [node.dir][node.x][node.y] + 1)) {
q [l1].push (temp);
c [temp.dir][temp.x][temp.y] = c [node.dir][node.x][node.y] + 1;
if (temp.x == F.x && temp.y == F.y) {
printf ("%d\n", c [temp.dir][temp.x][temp.y]);
return 0;
}
}
}
temp.x = node.x;
temp.y = node.y;
temp.dir = node.dir - 1;
if (temp.dir == -1)
temp.dir = 7;
if (temp.x >= 1 && temp.x <= n && temp.y >= 1 && temp.y <= m && a [temp.x][temp.y] == 0) {
if (c [temp.dir][temp.x][temp.y] == -1 || (c [temp.dir][temp.x][temp.y] != -1 && c [temp.dir][temp.x][temp.y] > c [node.dir][node.x][node.y] + 1)) {
q [l1].push (temp);
c [temp.dir][temp.x][temp.y] = c [node.dir][node.x][node.y] + 1;
if (temp.x == F.x && temp.y == F.y) {
printf ("%d\n", c [temp.dir][temp.x][temp.y]);
return 0;
}
}
}
}
}
printf ("-1\n");
return 0;
}