Pagini recente » Cod sursa (job #2222092) | Cod sursa (job #2263973) | Cod sursa (job #2263953) | Cod sursa (job #1866475) | Cod sursa (job #1773644)
#include <cstdio>
#include <queue>
#define DIM 503
#define DIMBUFF 100000
int di[] = {-1,-1,0,1,1, 1, 0,-1};
int dj[] = { 0, 1,1,1,0,-1,-1,-1};
using namespace std;
int V[DIM][DIM][8];
int a[DIM][DIM];
struct elem {
int i;
int j;
int d;
};
elem r;
deque<elem> L[3];
int n, m, i1, j1, i2, j2;
elem make_elem(int i, int j, int d) {
r.i = i;
r.j = j;
r.d = d;
return r;
}
inline int modul(int x) {
return ( x > 0 ? x : -x );
}
FILE * fin = fopen ("car.in", "r");
FILE *fout = fopen ("car.out", "w");
char buff[DIMBUFF];
int pp;
int numar() {
int val = 0;
while (!(buff[pp] >= '0' && buff[pp] <= '9')) {
pp++;
if (pp == DIMBUFF) {
fread(buff, 1, DIMBUFF, fin);
pp=0;
}
}
while (buff[pp] >= '0' && buff[pp] <= '9') {
val = val*10 + buff[pp] - '0';
pp++;
if (pp == DIMBUFF) {
fread(buff, 1, DIMBUFF, fin);
pp=0;
}
}
return val;
}
int main () {
n = numar();
m = numar();
i1 = numar();
j1 = numar();
i2 = numar();
j2 = numar();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
a[i][j] = numar();
a[i][0] = a[i][m+1] = 1;
}
for (register int i=0;i<=m+1;i++)
a[0][i] = a[n+1][i] = 1;
//fin>>a[i][j];
for (int i=0;i<8;i++) {
L[0].push_back(make_elem(i1, j1, i));
}
int p = 0;
int step = 1;
register int iv, jv, nextd, ci, cj, cd;
while (L[0].size() + L[1].size() + L[2].size()) {
while (L[p].size()) {
elem crt = L[p].front();
ci = crt.i;
cj = crt.j;
cd = crt.d;
L[p].pop_front();
if (!V[ci][cj][cd]) {
V[ci][cj][cd] = step;
if (ci == i2 && cj == j2) {
//fout<<step-1;
fprintf(fout, "%d", step-1);
return 0;
}
for (register int k=-1;k<=1;k++) {
nextd = cd + k;
nextd &= 7;
if (k == 0) {
iv = ci + di[ nextd ];
jv = cj + dj[ nextd ];
} else {
iv = ci;
jv = cj;
}
if (a[iv][jv] != 0)
continue;
if (V[iv][jv][nextd] == 0)
L[ (p+modul(k)) & 1 ].push_back(make_elem(iv, jv, nextd));
}
}
}
p = 1-p;
step++;
}
fprintf(fout, "-1");
// fout<<-1;
return 0;
}