Cod sursa(job #2821363)

Utilizator DordeDorde Matei Dorde Data 22 decembrie 2021 15:08:41
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 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 , c[9][9];
void getcost(){
    int c0[] = {0 , 3 , 2 , 1 , 4 , 1 , 2 , 3};
    for(int i = 0 ; i <= 8 ; ++ i)
        for(int j = 1 ; j <= 8 ; ++ j)
            c[i][j] = c0[(j - i + 8) % 8];
}
bool valid(int a , int b){
    return a && b && a <= n && b <= m && !mat[a][b];
}
struct Node{
    int x , y , w , d;
    Node(){
        x = y = w = d = 0;
    }
    Node(int A , int B , int C , int D){
        x = A , y = B , w = C , d = D;
    }
    bool operator > (Node r) const{
        return w > r.w;
    }
};
int main(){
    fin >> n >> m;
    if(min(n , m) == 0){
        fout << "-1\n";
        return 0;
    }
    int x1 , y1 , x2 , y2;
    fin >> x1 >> y1 >> x2 >> y2;
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= m ; ++ j)
            fin >> mat[i][j];
    if(mat[x1][y1] || mat[x2][y2]){
        fout << "-1\n";
        return 0;
    }
    getcost();
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= m ; ++ j)
            fill(dp[i][j] , dp[i][j] + 8 , inf);
    fill(dp[x1][y1] , dp[x1][y1] + 8 , 0);
    priority_queue<Node , vector<Node> , greater<Node>> q;
    for(int i = 0 ; i < 8 ; ++ i){
        int a = x1 + vx[i] , b = y1 + vy[i];
        if(valid(a , b)){
            q.push(Node(a , b , 0 , i));
            dp[a][b][i] = 0;
        }
    }
    if(make_pair(x1 , y1) == make_pair(x2 , y2)){
        fout << "0\n";
        return 0;
    }
    while(q.size()){
        Node cell = q.top();
        q.pop();
        for(int i = 0 ; i < 8 ; ++ i){
            int a = vx[i] + cell.x , b = vy[i] + cell.y;
            if(valid(a , b) && dp[a][b][i] > cell.w + c[cell.d][i]){
                dp[a][b][i] = cell.w + c[cell.d][i];
                q.push(Node(a , b , dp[a][b][i] , i));
            }
        }
    }
    if(*min_element(dp[x2][y2] , dp[x2][y2] + 8) == inf)
        fout << "-1\n";
    else
        fout << *min_element(dp[x2][y2] , dp[x2][y2] + 8);
    return 0;
}