Pagini recente » Cod sursa (job #2579511) | Cod sursa (job #2534100) | Cod sursa (job #3202699) | Cod sursa (job #1044881) | Cod sursa (job #2925930)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("car.in");
ofstream g ("car.out");
typedef pair <pair <int, int>, int> PIII;
constexpr int NMAX = 502;
int N, M;
int Start_i, Start_j, End_i, End_j;
int A[NMAX][NMAX];
void Read () {
f >> N >> M;
f >> Start_i >> Start_j;
f >> End_i >> End_j;
for (int i = 1; i <= N; ++ i )
for (int j = 1; j <= M; ++ j )
f >> A[i][j];
}
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
bool Good (int x, int y) {
return (0 < x && x <= N && 0 < y && y <= M && A[x][y] == 0);
}
int Best[NMAX][NMAX][8];
void Solve () {
if (A[Start_i][Start_j] == -1 || A[End_i][End_j] == -1) {
g << -1 << '\n';
return;
}
for (int i = 1; i <= N; ++ i )
for (int j = 1; j <= M; ++ j )
for (int k = 0; k < 8; ++ k )
Best[i][j][k] = -1;
queue < PIII > Q;
for (int k = 0; k < 8; ++ k ) {
Best[Start_i][Start_j][k] = 0;
Q.push({{Start_i, Start_j}, k});
}
while (!Q.empty()) {
PIII nod = Q.front();
Q.pop();
int x = nod.first.first;
int y = nod.first.second;
int k = nod.second;
int new_x = x + dx[k];
int new_y = y + dy[k];
if (Good(new_x, new_y) && (Best[new_x][new_y][k] == -1 || Best[new_x][new_y][k] > Best[x][y][k])) {
Best[new_x][new_y][k] = Best[x][y][k];
Q.push({{new_x, new_y}, k});
}
for (int o = -1; o <= 1; o += 2) {
int new_k = k + o;
if (new_k < 0) new_k = 7;
if (new_k > 7) new_k = 0;
if (Best[x][y][new_k] == -1 || Best[x][y][new_k] > Best[x][y][k] + 1) {
Best[x][y][new_k] = Best[x][y][k] + 1;
Q.push({{x, y}, new_k});
}
}
}
int ans = -1;
for (int i = 0; i < 8; ++ i ) {
if (Best[End_i][End_j][i] == -1) continue;
if (ans == -1 || ans > Best[End_i][End_j][i])
ans = Best[End_i][End_j][i];
}
g << ans << '\n';
}
int main () {
Read();
Solve();
return 0;
}