Cod sursa(job #2821461)

Utilizator DordeDorde Matei Dorde Data 22 decembrie 2021 17:00:17
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#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;
}