Pagini recente » Cod sursa (job #2611948) | Cod sursa (job #2287205) | Cod sursa (job #1755590) | Cod sursa (job #2486707) | Cod sursa (job #1041589)
#include <fstream>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
const int MAX_N = 505;
inline int const abs(int const x){return x > 0 ? x : -x;}
const int dx[] = {0,0, 1,1, 1,-1,-1,-1};
const int dy[] = {1,-1,1,0,-1, 1, 0,-1};
int bst[MAX_N][MAX_N][8];
int all[MAX_N][MAX_N];
bool bad[MAX_N][MAX_N];
struct state{
int x,y;
int from;
};
queue<state> Q;
ifstream in("car.in");
ofstream out("car.out");
int n,m;
int x0,y0;
int x1,y1;
int cost[100];
bool shift45(int orig, int nxt){
return dx[orig] - dy[orig] == dx[nxt] &&
dx[orig] + dy[orig] == dy[nxt];
}
bool shift90(int orig, int nxt){
return -dy[orig] == dx[nxt] &&
dx[orig] == dy[nxt];
}
int get_deg(int orig, int nxt){
if(orig == nxt)
return 0;
if(shift45(orig, nxt) || shift45(nxt, orig))
return 45;
if(shift90(orig, nxt) || shift90(nxt, orig))
return 90;
return -1;
}
void spread(){
state now;
now.x = x0;
now.y = y0;
memset(bst, 0x3f, sizeof(bst));
memset(all, 0x3f, sizeof(all));
int i,j;
for(int i = 0 ; i < 8 ; ++i) {
now.from = i;
bst[x0][y0][i] = 0;
Q.push(now);
}
while(!Q.empty()){
now = Q.front();
Q.pop();
for(int i = 0 ; i < 8 ; ++i){
const int next_x = now.x + dx[i],
next_y = now.y + dy[i];
int deg = get_deg(now.from, i);
if(deg == -1)
continue;
if(next_x < 1 || next_x > n || next_y < 1 || next_y > m)
continue;
if(bad[next_x][next_y])
continue;
if(all[next_x][next_y] + 2 < bst[now.x][now.y][now.from] + cost[deg]
|| bst[next_x][next_y][i] < bst[now.x][now.y][now.from] + cost[deg])
continue;
bst[next_x][next_y][i] = bst[now.x][now.y][now.from] + cost[deg];
Q.push((state){next_x,next_y,i});
if(bst[next_x][next_y][i] < all[next_x][next_y])
all[next_x][next_y] = bst[next_x][next_y][i];
}
}
}
int main(){
cost[0] = 0;
cost[45] = 1;
cost[90] = 2;
in >> n >> m;
in >> x0 >> y0;
in >> x1 >> y1;
for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= m ; ++j)
in >> bad[i][j];
spread();
int ans = -1;
for(int i = 0 ; i < 8 ; ++i)
if(ans == -1 || bst[x1][y1][i] < ans)
ans = bst[x1][y1][i];
if(ans == 0x3f3f3f3f)
ans = -1;
out << ans << "\n";
return 0;
}