Pagini recente » Cod sursa (job #1799907) | Cod sursa (job #2329073) | Cod sursa (job #2638621) | Cod sursa (job #2937987) | Cod sursa (job #2646991)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 505
int n,m,sx,sy,fx,fy,mn[NMAX][NMAX][8],cst[8][8];
bool mat[NMAX][NMAX];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
struct ceva{
int x,y,d,cst;
};
ceva Q[3][260000];
bool comp(ceva A, ceva B){
return A.cst > B.cst;
}
int main()
{
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
// cout << "500 500\n1 1 500 500\n";
// for (int i=1;i<=500;i++,cout << '\n')
// for (int j=1;j<=500;j++)
// if (j%2==0){
// if (j%4==2 && i==500 || j%4==0 && i==1) cout << 0 << ' ';
// else cout << 1 << ' ';
// }
// else
// cout << 0 << ' ';
//
// return 0;
cin >> n >> m;
cin >> sx >> sy >> fx >> fy;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
cin >> mat[i][j];
}
for (int i=0;i<=n+1;i++) mat[i][0] = mat[i][m+1] = 1;
for (int j=0;j<=m+1;j++) mat[0][j] = mat[n+1][j] = 1;
for (int i=0;i<8;i++){
for (int j=0;j<8;j++){
cst[i][j] = min(abs(j-i), 8 - max(i,j) + min(i,j));
}
}
memset(mn,0x3f,sizeof(mn));
for (int i=0;i<8;i++){
mn[sx][sy][i] = 0;
Q[0][++Q[0][0].d] = {sx, sy, i, 0};
}
int t = 0;
while (!(Q[0][0].d==0 && Q[1][0].d==0 && Q[2][0].d==0)){
for (int i=1;i<=Q[t][0].d;i++){
ceva crt = Q[t][i];
if (crt.cst > mn[crt.x][crt.y][crt.d]) continue;
if (crt.x == fx && crt.y == fy){
cout << crt.cst << '\n';
return 0;
}
// cerr << crt.x << ' ' << crt.y << ' ' << crt.d << ' ' << crt.cst << '\n';
for (int k=0;k<8;k++){
int x = crt.x + dx[k];
int y = crt.y + dy[k];
if (mat[x][y] == 1) continue;
int d = k;
if (cst[crt.d][k] > 2) continue;
int newCst = cst[crt.d][k] + crt.cst;
if (newCst < mn[x][y][d]){
mn[x][y][d] = newCst;
Q[(t + newCst) % 3][++Q[(t + newCst) % 3][0].d] = {x,y,d,newCst};
}
}
}
Q[t][0].d = 0;
t++;
t %= 3;
}
int ans = 1e9;
for (int i=0;i<8;i++) ans = min(ans, mn[fx][fy][i]);
if (ans > 1e8) cout << "-1\n";
else cout << ans << '\n';
return 0;
}