Pagini recente » Cod sursa (job #3192829) | Cod sursa (job #3265936) | Cod sursa (job #665814) | Cod sursa (job #2844090) | Cod sursa (job #2710564)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const short NMAX = 512;
short N, M, istart, jstart, istop, jstop;
bool a[NMAX][NMAX];
int l[2][NMAX * NMAX << 1], sz[2];
short viz[1 << 22], best[1 << 22], ans;
const int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};
bool inside(const int &lin, const int &col) {
return lin > 0 && col > 0 && lin <= N && col <= M;
}
void read() {
fin >> N >> M >> istart >> jstart >> istop >> jstop;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
fin >> a[i][j];
}
void solve() {
for(int k = 0; k < 8; ++k) {
int val = (istart << 12) + (jstart << 3) + k;
l[0][++sz[0]] = val;
viz[val] = best[val] = 1;
}
int ind = 0;
while(sz[ind]) {
int nxt = ind ^ 1;
for(int k = 1; k <= sz[ind]; ++k)
if(viz[l[ind][k]] == 1) {
int val = l[ind][k];
int dir = val & 7,
j = (val & (511 << 3)) >> 3,
i = (val & (511 << 12)) >> 12;
int iv = i + di[dir],
jv = j + dj[dir];
if(inside(iv, jv) && !a[iv][jv]) {
int nxt_val = (iv << 12) + (jv << 3) + dir;
if(!viz[nxt_val] || best[nxt_val] > best[val]) {
viz[nxt_val] = 1;
best[nxt_val] = best[val];
l[ind][++sz[ind]] = nxt_val;
}
}
if(!a[i][j]) {
dir = (dir + 1) % 8;
int nxt_val = (i << 12) + (j << 3) + dir;
if(!viz[nxt_val]) {
viz[nxt_val] = 1;
best[nxt_val] = best[val] + 1;
l[nxt][++sz[nxt]] = nxt_val;
}
nxt_val -= dir;
dir = (dir + 6) % 8;
nxt_val += dir;
if(!viz[nxt_val]) {
viz[nxt_val] = 1;
best[nxt_val] = best[val] + 1;
l[nxt][++sz[nxt]] = nxt_val;
}
}
if(i == istop && j == jstop) {
ans = best[val];
return;
}
viz[val] = 2;
}
sz[ind] = 0;
ind = nxt;
}
}
int main() {
read();
solve();
fout << ans - 1 << '\n';
}