Pagini recente » Cod sursa (job #3267384) | Cod sursa (job #2261235) | Cod sursa (job #2063198) | Cod sursa (job #1744711) | Cod sursa (job #1068206)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int N, M;
int v[512][512];
int dp[512][512][8];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int sx, sy, ex, ey;
int qx[1000000];
int qy[1000000];
int main() {
freopen("car.in", "r", stdin);
freopen("car.out", "w", stdout);
scanf("%d %d", &N, &M);
scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j) scanf("%d", &v[i][j]);
for (int i = 0; i <= N + 1; ++i) v[i][0] = v[i][M+1] = 1;
for (int i = 0; i <= M + 1; ++i) v[0][i] = v[N+1][i] = 1;
memset(dp, 333, sizeof(dp));
int INF = dp[0][0][0];
for (int i = 0; i < 8; ++i) dp[sx][sy][i] = 0;
qx[++qx[0]] = sx; qy[++qy[0]] = sy;
int best = INF;
for (int i = 1; i <= qx[0]; ++i) {
int nx = qx[i], ny = qy[i];
if (nx == ex && ny == ey)
for (int d = 0; d < 8; ++d) best = min(best, dp[nx][ny][d]);
for (int d = 0; d < 16; ++d) dp[nx][ny][d%8] = min(dp[nx][ny][d%8],1+min(dp[nx][ny][(d+7)%8], dp[nx][ny][(d+1)%8]));
for (int d = 0; d < 8; ++d) if (dp[nx][ny][d] < INF) {
if (v[nx+dx[d]][ny+dy[d]] == 0 && dp[nx+dx[d]][ny+dy[d]][d] > dp[nx][ny][d]) {
dp[nx+dx[d]][ny+dy[d]][d] = dp[nx][ny][d]; qx[++qx[0]] = nx + dx[d]; qy[++qy[0]] = ny + dy[d];
}
}
}
printf("%d\n", best >= INF ? -1 : best);
return 0;
}