Pagini recente » Cod sursa (job #3365971) | Cod sursa (job #3366003) | Cod sursa (job #3365998) | Cod sursa (job #3366002) | Cod sursa (job #3366285)
#include <bits/stdc++.h>
using namespace std;
int mat[1001][1001], dist[1001][1001][8], n, m;
int di[]={-1, -1, -1, 0, 1, 1, 1, 0}, dj[]={-1, 0, 1, 1, 1, 0, -1, -1};
queue<int> lst;
bool check(int x, int y) {
if (x>0 && x<=n && y>0 && y<=m && mat[x][y]==0) return true;
return false;
}
void lee(int a1, int a2) {
queue<pair<int, int>> q;
for (int i=0; i<8; i++) {
dist[a1][a2][i]=0;
q.push(make_pair(a1, a2));
lst.push(i);
}
while(!q.empty()) {
int i = q.front().first, j = q.front().second, l=lst.front();
q.pop();
lst.pop();
for(int k = 0; k < 8; k++) {
int x = i + di[k], y = j + dj[k];
int p;
p=min(max(k,l)-min(k, l), 8-max(k, l)+min(k, l));
//int p=k;
// if (max(k, l) - min(k, l) > 4) {
// if (k>l)
// l+=8;
// else
// p=k+8;
// }
//p=l-p;
//if (p<0)
// p=-p;
if (check(x, y) && dist[x][y][k] > dist[i][j][l] + p) {
dist[x][y][k] = dist[i][j][l]+p;
q.push(make_pair(x, y));
lst.push(k);
}
}
}
}
int main() {
ifstream cin("car.in");
ofstream cout("car.out");
cin >> n >> m;
int pl, pc, cl, cc;
cin >> pl >> pc >> cl >> cc;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mat[i][j];
for (int k = 0; k < 8; k++) {
dist[i][j][k]=1e9;
}
}
}
lee(pl, pc);
int ans=1e9;
for (int i=0; i<8; i++) {
ans=min(ans, dist[cl][cc][i]);
}
cout << ans << endl;
return 0;
}