Pagini recente » Cod sursa (job #2034428) | Cod sursa (job #1625909) | Cod sursa (job #1288924) | Cod sursa (job #2406650) | Cod sursa (job #1585420)
#include <fstream>
#include <cstring>
using namespace std;
const int kMaxN = 505, kInf = 0x3f3f3f3f;
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
ifstream fin("car.in");
ofstream fout("car.out");
int N, M, sx, sy, fx, fy;
char buffer[kMaxN * 2 + 2];
bool a[kMaxN][kMaxN];
int dist[kMaxN][kMaxN][8];
struct Node {
int x, y, d;
} q[3][kMaxN * kMaxN];
int qs[3];
void SetDist(int x, int y, int d, int cost) {
int qi = cost % 3;
q[qi][qs[qi]].x = x;
q[qi][qs[qi]].y = y;
q[qi][qs[qi]].d = d;
++qs[qi];
dist[x][y][d] = cost;
}
int main() {
(fin >> N >> M >> sx >> sy >> fx >> fy).ignore(1);
for (int i = 1; i <= N; ++i) {
fin.getline(buffer + 2, kMaxN * 2);
for (int j = 1; j <= M; ++j)
a[i][j] = (buffer[j << 1] == '0');
}
memset(dist, kInf, sizeof dist);
for (int i = 0; i < 8; ++i)
SetDist(sx, sy, i, 0);
for (int cost = 0; qs[0] + qs[1] + qs[2]; ++cost) {
int crt = cost % 3;
for (int i = 0; i < qs[crt]; ++i) {
int x = q[crt][i].x;
int y = q[crt][i].y;
int d = q[crt][i].d;
if ((x == fx && y == fy) || dist[x][y][d] != cost)
continue;
for (int i = -2; i <= 2; ++i) {
int nd = (d + i) & 7;
int nx = x + dx[nd];
int ny = y + dy[nd];
int ncost = cost + max(i, -i);
if (a[nx][ny] && ncost < dist[nx][ny][nd])
SetDist(nx, ny, nd, ncost);
}
}
qs[crt] = 0;
}
int ans = kInf;
for (int i = 0; i < 8; ++i)
ans = min(ans, dist[fx][fy][i]);
fout << (ans == kInf ? -1 : ans) << "\n";
return 0;
}