Pagini recente » Cod sursa (job #1451377) | Cod sursa (job #527306) | Cod sursa (job #1682460) | Cod sursa (job #2835922) | Cod sursa (job #1773608)
#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]);
//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;
while (L[0].size() + L[1].size() + L[2].size() != 0) {
while (L[p].size()) {
elem crt = L[p].front();
L[p].pop_front();
if (V[crt.i][crt.j][crt.d] == 0) {
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 (int k=-1;k<=1;k++) {
int nextd = (crt.d + k + 8) & 7, iv, jv;
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 (iv >= 1 && iv <= n && jv >= 1 && jv <= m && a[iv][jv] == 0 && V[iv][jv][nextd] == 0)
L[ (p+modul(k)) % 2 ].push_back(make_elem(iv, jv, nextd));
}
}
}
p = (p+1) % 2;
step++;
}
fprintf(fout, "-1");
// fout<<-1;
return 0;
}