Pagini recente » Cod sursa (job #3240960) | Cod sursa (job #619092) | Cod sursa (job #240918) | Cod sursa (job #1502715) | Cod sursa (job #2415649)
#include <bits/stdc++.h>
#define DEF 510
using namespace std;
struct pozitie {
int x;
int y;
int dir;
};
ifstream fin ("car.in");
ofstream fout ("car.out");
int n, m, M[DEF][DEF], dp[DEF][DEF][8], Fr[DEF][DEF][8];
const int INF = numeric_limits<int>::max();
int dx[] = { -1, -1, +0, +1, +1, +1, +0, -1 };
int dy[] = { +0, +1, +1, +1, +0, -1, -1, -1 };
pair < int, int > start, finish;
deque < pozitie > Q;
int main () {
fin >> n >> m >> start.first >> start.second >> finish.first >> finish.second;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
fin >> M[i][j];
for (int d = 0; d < 8; ++ d) {
dp[i][j][d] = INF;
}
}
}
for (int i = 1; i <= n; ++ i) {
M[i][0] = M[i][m + 1] = 1;
}
for (int j = 1; j <= m; ++ j) {
M[0][j] = M[n + 1][j] = 1;
}
for (int i = 0; i <= 7; ++ i) {
dp[start.first][start.second][i] = 0;
Q.push_back ({start.first, start.second, i});
}
while (!Q.empty ()) {
int x = Q.front().x;
int y = Q.front().y;
int dir = Q.front().dir;
Q.pop_front ();
int new_x = x + dx[dir];
int new_y = y + dy[dir];
if (M[new_x][new_y] == 0 and dp[new_x][new_y][dir] > dp[x][y][dir]) {
dp[new_x][new_y][dir] = dp[x][y][dir];
if (Fr[new_x][new_y][dir] == false) {
Fr[new_x][new_y][dir] = true;
Q.push_back ({new_x, new_y, dir});
}
}
int new_dir = (dir + 1) % 8;
if (dp[x][y][new_dir] > dp[x][y][dir] + 1) {
dp[x][y][new_dir] = dp[x][y][dir] + 1;
if (Fr[x][y][new_dir] == false) {
Fr[x][y][new_dir] = true;
Q.push_back ({x, y, new_dir});
}
}
new_dir = dir - 1;
if (new_dir < 0)
new_dir = 7;
if (dp[x][y][new_dir] > dp[x][y][dir] + 1) {
dp[x][y][new_dir] = dp[x][y][dir] + 1;
if (Fr[x][y][new_dir] == false) {
Fr[x][y][new_dir] = true;
Q.push_back ({x, y, new_dir});
}
}
}
int minim = INF;
for (int i = 0; i < 8; ++ i) {
minim = min (minim, dp[finish.first][finish.second][i]);
}
if (minim == INF)
fout << "-1";
else
fout << minim;
return 0;
}