Pagini recente » Cod sursa (job #1846127) | Clasament oni_gim2016 | Cod sursa (job #2449489) | Cod sursa (job #1472326) | Cod sursa (job #2821461)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int const N = 501 , inf = (1 << 30);
int const vx[] = {1 , 1 , 0 , -1 , -1 , -1 , 0 , 1};
int const vy[] = {0 , 1 , 1 , 1 , 0 , -1 , -1 , -1};
int mat[N][N] , dp[N][N][9] , n , m , xs , ys , xf , yf;
bitset<8> viz[N][N];
struct Node{
int x , y , dir;
Node(){
}
Node(int A , int B , int C){
x = A , y = B , dir = C;
}
};
bool valid(int a , int b){
return a && b && a <= n && b <= m;
}
int main(){
fin >> n >> m >> xs >> ys >> xf >> yf;
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j)
fin >> mat[i][j];
deque<Node>q;
for(int d = 0 ; d < 8 ; ++ d){
dp[xs][ys][d] = -1;
q.push_back(Node(xs , ys , d));
}
while(!q.empty()){
Node now = q.front();
q.pop_front();
if(viz[now.x][now.y][now.dir])
continue;
viz[now.x][now.y][now.dir] = 1;
if(now.x == xf && now.y == yf){
fout << dp[now.x][now.y][now.dir] << '\n';
return 0;
}
int nx = now.x + vx[now.dir] , ny = now.y + vy[now.dir];
if(valid(nx , ny) && !mat[nx][ny]){
dp[nx][ny][now.dir] = dp[now.x][now.y][now.dir];
q.push_front(Node(nx , ny , now.dir));
}
for(auto &i : {1 , -1}){
if(viz[now.x][now.y][(8 + now.dir + i) % 8])
continue;
dp[now.x][now.y][(8 + now.dir + i) % 8] = 1 + dp[now.x][now.y][now.dir];
q.push_back(Node(now.x , now.y , (8 + now.dir + i) % 8));
}
}
return 0;
}