Pagini recente » Cod sursa (job #575209) | Cod sursa (job #310273) | Cod sursa (job #666152) | Cod sursa (job #646277) | Cod sursa (job #2651148)
#include <bits/stdc++.h>
#define STOP fout.close(); exit(EXIT_SUCCESS);
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
///***********************
const int NMAX = 503, OO = 2e9, ndirs = 8,
dirI[] = {-1,-1,0,1,1,1,0,-1},
dirJ[] = {0,1,1,1,0,-1,-1,-1};
struct Elem {
int i, j, dir, cost;
};
queue<Elem> q0, q1;
int n, m, si, sj, fi, fj, dp[NMAX][NMAX][10];
bool a[NMAX][NMAX];
inline bool isOk(int i, int j) {
return i >= 1 && j >= 1 && i <= n && j <= m && !a[i][j];
}
void read() {
fin >> n >> m >> si >> sj >> fi >> fj;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
fin >> a[i][j];
for (int dir = 0; dir < ndirs; dir++)
dp[i][j][dir] = OO;
}
for (int dir = 0; dir < ndirs; dir++)
q0.push({.i = si, .j = sj, .dir = dir, .cost = 0});
}
void lee() {
int i, j, k;
Elem currE, newE;
while (q0.size()) {
while (q0.size()) {
currE = q0.front();
q0.pop();
newE.i = currE.i + dirI[currE.dir];
newE.j = currE.j + dirJ[currE.dir];
newE.dir = currE.dir, newE.cost = currE.cost;
if (isOk(newE.i, newE.j) && dp[newE.i][newE.j][newE.dir] > newE.cost) {
dp[newE.i][newE.j][newE.dir] = newE.cost;
q0.push(newE);
}
newE.cost++;
newE.dir = (newE.dir + 1) % ndirs;
newE.i = currE.i;
newE.j = currE.j;
if (isOk(newE.i, newE.j) && dp[newE.i][newE.j][newE.dir] > newE.cost) {
dp[newE.i][newE.j][newE.dir] = newE.cost;
q1.push(newE);
}
newE.dir -= 2;
if (newE.dir < 0)
newE.dir = ndirs - 1;
if (isOk(newE.i, newE.j) && dp[newE.i][newE.j][newE.dir] > newE.cost) {
dp[newE.i][newE.j][newE.dir] = newE.cost;
q1.push(newE);
}
}
while (q1.size()) {
q0.push(q1.front());
q1.pop();
}
}
}
void display() {
int ans = *dp[fi][fj];
for (int i = 1; i < ndirs; i++)
ans = min(ans, dp[fi][fj][i]);
fout << ((ans == OO) ? -1 : ans) << '\n';
}
int main() {
read();
lee();
display();
STOP
}