Cod sursa(job #2821638)

Utilizator DordeDorde Matei Dorde Data 22 decembrie 2021 20:19:18
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 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] , viz[N][N][9] , n , m , xs , ys , xf , yf;
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] = 0;
        viz[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] != 1)
            continue;
        int nx = now.x + vx[now.dir] , ny = now.y + vy[now.dir];
        if(valid(nx , ny) && !mat[nx][ny] &&(!viz[nx][ny][now.dir] || dp[now.x][now.y][now.dir] < dp[nx][ny][now.dir])){
            dp[nx][ny][now.dir] = dp[now.x][now.y][now.dir];
            viz[nx][ny][now.dir] = 1;
            q.push_front(Node(nx , ny , now.dir));
        }
        if(!mat[now.x][now.y]){
            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];
                viz[now.x][now.y][(8 + now.dir + i) % 8] = 1;
                q.push_back(Node(now.x , now.y , (8 + now.dir + i) % 8));
            }
        }
        if(now.x == xf && now.y == yf){
            fout << dp[now.x][now.y][now.dir] << '\n';
            return 0;
        }
        viz[now.x][now.y][now.dir] = 2;
    }
    return 0;
}