Pagini recente » Cod sursa (job #2620272) | Cod sursa (job #3267000) | Cod sursa (job #960877) | Cod sursa (job #2988550) | Cod sursa (job #2415716)
#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 = 0x3f3f3f3f;
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;
queue < 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 <= 7; ++ d) {
dp[i][j][d] = INF;
}
}
}
for (int i = 0; i <= 7; ++ i) {
dp[start.first][start.second][i] = 0;
Fr[start.first][start.second][i] = 1;
Q.push ({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 ();
int new_x = x + dx[dir];
int new_y = y + dy[dir];
while (new_x >= 1 and new_x <= n and new_y >= 1 and new_y <= m and 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 ({new_x, new_y, dir});
}
new_x += dx[dir];
new_y += dy[dir];
}
int new_dir = ( (dir == 7) ? 0 : (dir + 1) );
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 ({x, y, new_dir});
}
}
new_dir = ( (dir == 0) ? 7 : (dir - 1) );
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 ({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;
}