Pagini recente » Cod sursa (job #3214511) | Cod sursa (job #1029900) | Cod sursa (job #3242362) | Cod sursa (job #2883283)
#include <bits/stdc++.h>
#define Nmax 505
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
typedef vector < pair < int, int > > VIP;
typedef vector < int > VI;
const int oo = 1 << 28;
int n, m, xs, ys, xf, yf;
int M[Nmax][Nmax], D[Nmax][Nmax][11];
struct chestie{
int x, y, d;
};
queue < chestie > Q;
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
bool inside(int i, int j) { return i >= 1 && j >= 1 && i <= n && j <= m && M[i][j] == 0; }
int calculate_cost(int d1, int d2){
int p = abs(d2 - d1);
return min(p, 8 - p);
}
void Bfs(int x, int y){
for(int d = 1; d <= 8; ++d){
Q.push( { x, y, d + 1 });
D[x][y][d] = 0;
}
while(Q.size()){
x = Q.front().x;
y = Q.front().y;
int direction = Q.front().d;
for(int d = 0; d < 8; ++d){
int new_x = x + dx[d];
int new_y = y + dy[d];
if(inside(new_x, new_y) && D[new_x][new_y][d] > calculate_cost(d , direction) + D[x][y][direction]){
Q.push( { new_x, new_y, d } );
D[new_x][new_y][d] = calculate_cost(d , direction) + D[x][y][direction];
}
}
Q.pop();
}
}
int main() {
fin >> n >> m;
fin >> xs >> ys >> xf >> yf;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
fin >> M[i][j];
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= m; ++j)
for(int k = 0; k <= 8; ++k)
D[i][j][k] = oo;
Bfs(xs, ys);
int ans = oo;
for(int i = 0; i < 8; ++i)
ans = min(ans, D[xf][yf][i]);
if(ans == oo)
fout << -1;
else
fout << ans;
return 0;
}