Pagini recente » Cod sursa (job #2650918) | Cod sursa (job #2181546) | Cod sursa (job #1271016) | Cod sursa (job #1773615) | Cod sursa (job #1773627)
#include <cstdio>
#include <queue>
#define DIM 503
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;
};
deque<elem> L[3];
int n, m, i1, j1, i2, j2;
elem make_elem(int i, int j, int d) {
elem r;
r.i = i;
r.j = j;
r.d = d;
return r;
}
inline int modul(int x) {
return ( x > 0 ? x : -x );
}
int main () {
FILE * fin = fopen ("car.in", "r");
FILE *fout = fopen ("car.out", "w");
fscanf(fin,"%d %d %d %d %d %d", &n, &m, &i1, &j1, &i2, &j2);
//fin>>n>>m;
//fin>>i1>>j1>>i2>>j2;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
fscanf(fin, "%d", &a[i][j]);
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;
while (L[0].size() + L[1].size() + L[2].size()) {
while (L[p].size()) {
elem crt = L[p].front();
L[p].pop_front();
if (!V[crt.i][crt.j][crt.d]) {
V[crt.i][crt.j][crt.d] = step;
if (crt.i == i2 && crt.j == j2) {
//fout<<step-1;
fprintf(fout, "%d", step-1);
return 0;
}
for (register int k=-1;k<=1;k++) {
nextd = crt.d + k;
nextd &= 7;
if (k == 0) {
iv = crt.i + di[ nextd ];
jv = crt.j + dj[ nextd ];
} else {
iv = crt.i;
jv = crt.j;
}
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;
}