Pagini recente » Cod sursa (job #2643166) | Cod sursa (job #1423528)
#include <fstream>
#include <cstring>
#define DIM 520
using namespace std;
ifstream fin ("car.in" );
ofstream fout("car.out");
int N, M, i, j, K, ok, minim, p, u;
int A[DIM][DIM], D[DIM][DIM][9];
int F[DIM][DIM], ist, jst, ifi, jfi;
int C[3][DIM*DIM], d, iv, jv, jc, ic;
int diri[] = {-1,-1,-1, 0, 1, 1, 1, 0};
int dirj[] = {-1, 0, 1, 1, 1, 0,-1,-1};
void SetUp(){
fin >> N >> M;
fin >> ist >> jst;
fin >> ifi >> jfi;
for(i = 1; i <= N; i ++)
for(j = 1; j <= M; j ++)
fin >> A[i][j];
memset(D, -1, sizeof(D));
p = 2; u = 1;
C[1][u] = ist;
C[2][u] = jst;
F[ist][jst] = 2;
memset(D[ist][jst], 0, sizeof(D[ist][jst]));
for(d = 0; d <= 7; d ++){
iv = ist + diri[d];
jv = jst + dirj[d];
if(iv >= 1 && iv <= N)
if(jv >= 1 && jv <= M)
if(A[iv][jv] == 0){
u ++;
C[1][u] = iv;
C[2][u] = jv;
F[iv][jv] = 2;
D[iv][jv][d] = 0;
}
}
return;
}
void BFS(){
while(p <= u){
ic = C[1][p];
jc = C[2][p];
F[ic][jc] = 2;
for(d = 0; d <= 7; d ++){
iv = ic + diri[d];
jv = jc + dirj[d];
if(iv >= 1 && iv <= N)
if(F[iv][jv] != 2)
if(jv >= 1 && jv <= M)
if(A[iv][jv] == 0){
if(F[iv][jv] == 0){
u ++;
C[1][u] = iv;
C[2][u] = jv;
F[iv][jv] = 1;
}
if(D[iv][jv][d] == -1)
D[iv][jv][d] = DIM*DIM;
if(D[iv][jv][d] > D[ic][jc][(d+8)%8] + 0 && D[ic][jc][(d+8)%8] != -1)
D[iv][jv][d] = D[ic][jc][(d+8)%8] + 0;
if(D[iv][jv][d] > D[ic][jc][(d+9)%8] + 1 && D[ic][jc][(d+9)%8] != -1)
D[iv][jv][d] = D[ic][jc][(d+9)%8] + 1;
if(D[iv][jv][d] > D[ic][jc][(d+7)%8] + 1 && D[ic][jc][(d+7)%8] != -1)
D[iv][jv][d] = D[ic][jc][(d+7)%8] + 1;
if(D[iv][jv][d] > D[ic][jc][(d+10)%8] + 2 && D[ic][jc][(d+10)%8] != -1)
D[iv][jv][d] = D[ic][jc][(d+10)%8] + 2;
if(D[iv][jv][d] > D[ic][jc][(d+6)%8] + 2 && D[ic][jc][(d+6)%8] != -1)
D[iv][jv][d] = D[ic][jc][(d+6)%8] + 2;
}
}
p ++;
}
return;
}
void Finish(){
minim = DIM * DIM;
for(d = 0; d <= 7; d ++)
if(D[ifi][jfi][d] < minim && D[ifi][jfi][d] != -1)
minim = D[ifi][jfi][d];
if(minim == DIM * DIM)
fout << -1;
else
fout << minim;
return;
}
int main(){
SetUp();
BFS();
Finish();
return 0;
}