Pagini recente » Cod sursa (job #666175) | Cod sursa (job #646612) | Cod sursa (job #1556410) | Cod sursa (job #2262118) | Cod sursa (job #2647000)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 505
int n,m,sx,sy,fx,fy,mn[NMAX][NMAX][8],cst[8][8],lg[3];
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()
{
cin.sync_with_stdio(false);
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));
}
}
if (mat[sx][sy] == 1 || mat[fx][fy] == 1){
cout << -1 << '\n';
return 0;
}
memset(mn,0x3f,sizeof(mn));
for (int i=0;i<8;i++){
mn[sx][sy][i] = 0;
Q[0][++lg[0]] = {sx, sy, i, 0};
}
int t = 0;
while (!(lg[0]==0 && lg[1]==0 && lg[2]==0)){
for (int i=1;i<=lg[t];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=((crt.d+6)&7);k!=((crt.d+3)&7);k = (k+1) & 7){
int x = crt.x + dx[k];
int y = crt.y + dy[k];
if (mat[x][y] == 1) continue;
int newCst = cst[crt.d][k] + crt.cst;
if (newCst < mn[x][y][k]){
mn[x][y][k] = newCst;
int t2 = t + cst[crt.d][k];
if (t2 >= 3) t2 -= 3;
Q[t2][++lg[t2]] = {x,y,k,newCst};
}
}
}
lg[t] = 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;
}