Pagini recente » Cod sursa (job #2292475) | Cod sursa (job #400373) | Cod sursa (job #3254390) | Cod sursa (job #1463410) | Cod sursa (job #1703304)
#include<fstream>
#include<deque>
#define INF 1000000000
using namespace std;
int n, m, i, j, ii1, jj1, ii2, jj2, dir, k, iv, jv, lg, sol, ab;
int a[505][505], d[505][505][8];
struct elem{
short x;
short y;
char dirr;
};
deque<elem> c[5];
elem aux, ii;
int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};
ifstream fin("car.in");
ofstream fout("car.out");
int cost(int a, int b){
if(a > b){
swap(a, b);
}
int x = min(b - a, a + 8 - b);
return x;
}
int mod(int x){
if(x < 3){
return x;
}
else{
return x - 3;
}
}
int main(){
fin>> n >> m >> ii1 >> jj1 >> ii2 >> jj2;
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
fin>> a[i][j];
for(dir = 0; dir < 8; dir++){
d[i][j][dir] = INF;
}
}
}
for(dir = 0; dir < 8; dir++){
d[ii1][jj1][dir] = 0;
aux.x = ii1;
aux.y = jj1;
aux.dirr = dir;
c[0].push_back(aux);
}
lg = n * m * 3;
k = 0;
for(i = 0; i <= lg; i++){
while(!c[k].empty()){
ii = c[k].front();
if(d[ii.x][ii.y][ii.dirr] == i){
d[ii.x][ii.y][ii.dirr] = i;
for(dir = 0; dir < 8; dir++){
iv = ii.x + di[dir];
jv = ii.y + dj[dir];
ab = cost(dir, ii.dirr);
if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && a[iv][jv] == 0 && d[iv][jv][dir] > d[ii.x][ii.y][ii.dirr] + ab){
d[iv][jv][dir] = d[ii.x][ii.y][ii.dirr] + ab;
aux.x = iv;
aux.y = jv;
aux.dirr = dir;
if(ab <= 2){
c[ mod(k + ab)].push_back(aux);
}
}
}
}
c[k].pop_front();
}
k = mod(k + 1);
}
sol = INF;
for(i = 0; i < 8; i++){
sol = min(sol, d[ii2][jj2][i]);
}
if(sol == INF){
fout<<"-1\n";
return 0;
}
fout<< sol <<"\n";
return 0;
}