Pagini recente » Cod sursa (job #2963764) | Cod sursa (job #704733) | Cod sursa (job #2017299) | Cod sursa (job #403985) | Cod sursa (job #1603553)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500;
const int NUM_DIR = 8;
const int INF = 0x3f3f3f3f;
const int DIR[][2] = { {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1} };
bool pass[MAX_N + 1][MAX_N + 1];
deque <int> Q;
int D[MAX_N + 1][MAX_N + 1][NUM_DIR];
inline
int codify(const pair <pair <int, int>, int> &state) {
return (state.second << 18) | (state.first.second << 9) | state.first.first;
}
inline
pair <pair <int, int>, int> decode(const int &state) {
return make_pair(make_pair(state & 511, (state >> 9) & 511), state >> 18);
}
int main() {
ifstream fin("car.in");
ofstream fout("car.out");
fin.tie(0);
fout.tie(0);
ios_base::sync_with_stdio(false);
int N, M;
pair <int, int> startPos, endPos;
fin >> N >> M >> startPos.first >> startPos.second >> endPos.first >> endPos.second;
for (int i = 1; i <= N; ++ i) {
for (int j = 1; j <= M; ++ j) {
int x; fin >> x;
pass[i][j] = x ^ 1;
}
}
memset(D, 0x3f, sizeof(D));
for (int i = 0; i < NUM_DIR; ++ i) {
D[startPos.first][startPos.second][i] = 0;
Q.push_back(codify(make_pair(startPos, i)));
}
while (!Q.empty()) {
const pair< pair <int, int>, int> state = decode(Q.front());
Q.pop_front();
const int x = state.first.first;
const int y = state.first.second;
const int currentDir = state.second;
const int cost = D[x][y][currentDir];
for (int j = -1; j <= 1; ++ j) {
int newDir = (currentDir + j + NUM_DIR) & 7;
int X, Y;
if (j == 0) {
X = x + DIR[newDir][0];
Y = y + DIR[newDir][1];
} else {
X = x;
Y = y;
}
if (X <= 0 || X > N || Y > M || Y <= 0 || !pass[X][Y]) {
continue;
}
if (D[X][Y][newDir] > cost + (j != 0)) {
D[X][Y][newDir] = cost + (j != 0);
if (j != 0) {
Q.push_back(codify(make_pair(make_pair(X, Y), newDir)));
} else {
Q.push_front(codify(make_pair(make_pair(X, Y), newDir)));
}
}
}
}
int minCost = INF;
for (int i = 0; i < NUM_DIR; ++ i) {
if (D[endPos.first][endPos.second][i] < minCost) {
minCost = D[endPos.first][endPos.second][i];
}
}
if (minCost == INF) {
minCost = -1;
}
fout << minCost << '\n';
fout.close();
return 0;
}