Pagini recente » Cod sursa (job #2188554) | Cod sursa (job #802940) | Cod sursa (job #511264) | Cod sursa (job #1101430) | Cod sursa (job #203892)
Cod sursa(job #203892)
#include <stdio.h>
#include <string.h>
int c[250010];
int u[250010];
int n, m;
int a[510][510];
char viz[8][510][510];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
/*
while (1) {
while (pc <= qc) {
x = c[pc] & 511;
y = (c[pc] >> 9) & 511;
if (x == xf && y == yf) {
e = 1;
break;
}
dir = c[pc] >> 18;
//modific pe cine vizitez
if (!viz[dir][x + dx[dir]][y + dy[dir]] && !a[x + dx[dir]][y + dy[dir]]) {
c[++qc] = x + dx[dir] + ((y + dy[dir]) << 9) + (dir << 18);
viz[dir][x + dx[dir]][y + dy[dir]] = 1;
}
++pc;
}
for (i = 0; i <= qc; i++) {
x = c[i] & 511;
y = (c[i] >> 9) & 511;
dir = c[i] >> 18;
if (!viz[(dir + 1) & 7][x][y]) {
u[++qu] = x + (y << 9) + (((dir + 1) & 7) << 18);
viz[(dir + 1) & 7][x][y] = 1;
}
--dir;
//updatez
if (dir < 0) dir = 7;
if (!viz[dir][x][y]) {
u[++qu] = x + (y << 9) + (dir << 18);
viz[dir][x][y] = 1;
}
}
if (e > 0) {
break;
}
if (qu == -1) {
cost = -1;
break;
}
++cost;
//golesk matricea
memcpy(c, u, sizeof(c));
pc = 0;
qc = qu;
qu = -1;
}
*/
int main() {
int cost = 0, e = 0, i, j, pc = 0, qc = 7, qu = -1, x, y, xb, yb, xf, yf, dir;
freopen("car.in", "r", stdin);
freopen("car.out", "w", stdout);
scanf("%d %d", &n, &m);
scanf("%d %d %d %d", &xb, &yb, &xf, &yf);
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
//init
for (i = 0; i <= n + 1; ++i) {
a[i][0] = 1;
a[i][m + 1] = 1;
}
//init lap
for (j = 0; j <= m + 1; ++j) {
a[0][j] = 1;
a[n + 1][j] = 1;
}
//dirs
for (i = 0; i < 8; ++i) {
c[i] = xb + (yb << 9) + (i << 18);
viz[i][xb][yb] = 1;
}
while (1) {
while (pc <= qc) {
x = c[pc] & 511;
y = (c[pc] >> 9) & 511;
if (x == xf && y == yf) {
e = 1;
break;
}
dir = c[pc] >> 18;
//modific pe cine vizitez
if (!viz[dir][x + dx[dir]][y + dy[dir]] && !a[x + dx[dir]][y + dy[dir]]) {
c[++qc] = x + dx[dir] + ((y + dy[dir]) << 9) + (dir << 18);
viz[dir][x + dx[dir]][y + dy[dir]] = 1;
}
++pc;
}
for (i = 0; i <= qc; i++) {
x = c[i] & 511;
y = (c[i] >> 9) & 511;
dir = c[i] >> 18;
if (!viz[(dir + 1) & 7][x][y]) {
u[++qu] = x + (y << 9) + (((dir + 1) & 7) << 18);
viz[(dir + 1) & 7][x][y] = 1;
}
--dir;
//updatez
if (dir < 0) dir = 7;
if (!viz[dir][x][y]) {
u[++qu] = x + (y << 9) + (dir << 18);
viz[dir][x][y] = 1;
}
}
if (e > 0) break;
if (qu == -1) {
cost = -1;
break;
}
++cost;
for (long ipr = 1; ipr <= 250000; ++ipr) {
c[ipr] = u[ipr];
}
//memcpy(c, u, sizeof(c));
pc = 0;
qc = qu;
qu = -1;
}
//afla();
printf("%d\n", cost);
return 0;
}