Cod sursa(job #2883287)

Utilizator BorodiBorodi Bogdan Borodi Data 1 aprilie 2022 13:17:37
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <string>
#include <bitset>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <bitset>
#include <stack>
#include <unordered_map>
#define Nmax 505
using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

typedef vector < pair < int, int > > VIP;
typedef vector < int > VI;

const int oo = 1 << 28;

int n, m, xs, ys, xf, yf;
int M[Nmax][Nmax], D[Nmax][Nmax][9];

struct chestie{
    int x, y, d;
};

queue < chestie > Q;

int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

bool inside(int i, int j) { return i >= 1 && j >= 1 && i <= n && j <= m && M[i][j] == 0; }

int calculate_cost(int d1, int d2){
    int p = abs(d2 - d1);
    return min(p, 8 - p);
}

void Bfs(int x, int y){
    for(int d = 0; d < 8; ++d){
        Q.push( { x, y, d });
        D[x][y][d] = 0;    
    }

    while(Q.size()){
        x = Q.front().x;
        y = Q.front().y;
        int direction = Q.front().d;
 
        for(int d = 0; d < 8; ++d){
            int new_x = x + dx[d];
            int new_y = y + dy[d];

            if(inside(new_x, new_y) && D[new_x][new_y][d] > calculate_cost(d , direction) + D[x][y][direction]){
                Q.push( { new_x, new_y, d } );
                D[new_x][new_y][d] = calculate_cost(d , direction) + D[x][y][direction];
            }
        }
        Q.pop();
    }
}

int main() {
    fin >> n >> m;
    fin >> xs >> ys >> xf >> yf;

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            fin >> M[i][j];    

    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
            for(int k = 0; k < 8; ++k)
                D[i][j][k] = oo;

    Bfs(xs, ys);

    int ans = oo;

    for(int i = 0; i < 8; ++i)
        ans = min(ans, D[xf][yf][i]);

    if(ans == oo)
        fout << -1;
    else
        fout << ans;

    return 0;   
}