Pagini recente » Cod sursa (job #1816804) | Cod sursa (job #597235) | Cod sursa (job #834655) | Cod sursa (job #1010845) | Cod sursa (job #129111)
Cod sursa(job #129111)
#include <stdio.h>
#include <string.h>
int n, m;
int a[510][510];
int dx[] = {-1,-1, 0, 1, 1, 1, 0,-1};
int dy[] = { 0, 1, 1, 1, 0,-1,-1,-1};
int cur[2000010];
int urm[2000010];
char viz[8][510][510];
int main()
{
int i, j, pc, qc, pu, qu, 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]);
for (i = 0; i <= n+1; i++)
{
a[i][0] = 1;
a[i][m+1] = 1;
}
for (j = 0; j <= m+1; j++)
{
a[0][j] = 1;
a[n+1][j] = 1;
}
for (i = 0; i < 8; i++)
{
cur[i] = xb + (yb << 9) + (i << 18);
viz[i][xb][yb] = 1;
}
pc = 0;
qc = 7;
pu = 0;
qu = -1;
int cost = 0;
int e = 0;
while (1)
{
//expandez cur pana nu mai pot
while (pc <= qc)
{
x = cur[pc] & 511;
y = (cur[pc] >> 9) & 511;
if (x == xf && y == yf)
{
e = 1;
break;
}
dir = cur[pc] >> 18;
// acu mut una in directie
if (!viz[dir][x + dx[dir]][y + dy[dir]] && !a[x + dx[dir]][y + dy[dir]])
{
cur[++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 = cur[i] & 511;
y = (cur[i] >> 9) & 511;
dir = cur[i] >> 18;
// il mut cu o directie in plus
if (!viz[(dir + 1) & 7][x][y])
{
urm[++qu] = x + (y << 9) + (((dir + 1) & 7) << 18);
viz[(dir + 1) & 7][x][y] = 1;
}
//il mut cu o directie in minus
dir--;
if (dir < 0) dir = 7;
if (!viz[dir][x][y])
{
urm[++qu] = x + (y << 9) + (dir << 18);
viz[dir][x][y] = 1;
}
}
if (e) break;
if (qu == -1)
{
cost = -1;
break;
}
cost ++;
memcpy(cur, urm, sizeof(cur));
pc = 0;
qc = qu;
qu = -1;
}
printf("%d\n", cost);
fclose(stdin);
fclose(stdout);
return 0;
}