Pagini recente » Cod sursa (job #2569321) | Cod sursa (job #438973) | Cod sursa (job #734482) | Cod sursa (job #2290932) | Cod sursa (job #1703433)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int dim = 505;
const int inf = 0x3f3f3f3f;
const int dx[] = { 1, 1, 1, 0, -1, -1, -1, 0 };
const int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int a[dim][dim], dp[dim][dim][8];
queue<int> que[2];
inline int makeState(int x, int y, int dir) {
return (dir << 18) + (x << 9) + y;
}
inline int getX(int state) {
return (state >> 9) & ((1 << 9) - 1);
}
inline int getY(int state) {
return state & ((1 << 9) - 1);
}
inline int getDir(int state) {
return state >> 18;
}
int main() {
int n, m, startX, startY, finishX, finishY;
fin >> n >> m >> startX >> startY >> finishX >> finishY;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
fin >> a[i][j];
for (int dir = 0; dir < 8; ++dir)
dp[i][j][dir] = inf;
}
}
int now = 0, nxt = 1;
for (int dir = 0; dir < 8; ++dir) {
que[now].push(makeState(startX, startY, dir));
dp[startX][startY][dir] = 0;
}
int sol = -1;
for (int cost = 0; !(que[0].empty() && que[1].empty()) && sol == -1; ++cost, swap(now, nxt)) {
while (!que[now].empty() && sol == -1) {
int cur = que[now].front();
que[now].pop();
int x = getX(cur);
int y = getY(cur);
int dir = getDir(cur);
if (x == finishX && y == finishY) {
sol = cost;
continue;
}
int nxtX = x + dx[dir];
int nxtY = y + dy[dir];
if (1 <= nxtX && nxtX <= n && 1 <= nxtY && nxtY <= m && a[nxtX][nxtY] == 0 && cost < dp[nxtX][nxtY][dir]) {
dp[nxtX][nxtY][dir] = cost;
que[now].push(makeState(nxtX, nxtY, dir));
}
int nxtDir = (dir + 1) % 8;
if (cost + 1 < dp[x][y][nxtDir]) {
dp[x][y][nxtDir] = cost + 1;
que[nxt].push(makeState(x, y, nxtDir));
}
nxtDir = (dir + 7) % 8;
if (cost + 1 < dp[x][y][nxtDir]) {
dp[x][y][nxtDir] = cost + 1;
que[nxt].push(makeState(x, y, nxtDir));
}
}
}
fout << sol << '\n';
return 0;
}
//Trust me, I'm the Doctor!