Pagini recente » Cod sursa (job #31759) | Cod sursa (job #3186270) | Cod sursa (job #1763173) | Cod sursa (job #824107) | Cod sursa (job #1491084)
#include <fstream>
#include <queue>
#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;
bool a[kMaxN][kMaxN];
int dcost[8][8];
int dist[kMaxN][kMaxN][8];
struct Node {
int x, y, d;
Node(int x, int y, int d) : x(x), y(y), d(d) {}
};
queue<Node> q[3];
bool QueuesNotEmpty() {
for (int i = 0; i < 3; ++i)
if (!q[i].empty()) return true;
return false;
}
int main() {
for (int i = 0; i < 8; ++i)
for (int j = 0; j < 8; ++j)
dcost[i][j] = min((i - j) & 7, (j - i) & 7);
fin >> N >> M >> sx >> sy >> fx >> fy;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j) {
char c;
fin >> c;
if (c == '0')
a[i][j] = true;
}
memset(dist, kInf, sizeof dist);
for (int i = 0; i < 8; ++i) {
q[0].emplace(sx, sy, i);
dist[sx][sy][i] = 0;
}
for (int cost = 0; QueuesNotEmpty(); ++cost) {
int crt = cost % 3;
while (!q[crt].empty()) {
int x = q[crt].front().x;
int y = q[crt].front().y;
int d = q[crt].front().d;
q[crt].pop();
if (dist[x][y][d] != cost)
continue;
for (int nd = 0; nd < 8; ++nd) {
if (dcost[d][nd] > 2)
continue;
int nx = x + dx[nd];
int ny = y + dy[nd];
int ncost = cost + dcost[d][nd];
if (a[nx][ny] && ncost < dist[nx][ny][nd]) {
dist[nx][ny][nd] = ncost;
q[ncost % 3].emplace(nx, ny, nd);
}
}
}
}
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;
}