Cod sursa(job #2641080)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 9 august 2020 21:32:51
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 500;
const int INF = 2.e9;
int di[]= {-1 , -1 , 0 , 1 , 1 , 1 , 0 , -1};
int dj[]= {0 , 1 , 1 , 1 , 0 , -1 , -1 , -1};
bool a[NMAX + 5][NMAX + 5];
int d[NMAX * NMAX + 5][9] , n , m;
struct car
{
    int nod , cost , dir;
    car(int x = 0 , int y = 0 , int z = 0)
    {
        nod = x;
        cost = y;
        dir = z;
    }
};
bool operator<(const car& a , const car& b)
{
    return a.cost > b.cost;
}
vector <car> G[NMAX + 5][9];
int valid(int x , int y)
{
    if(x >= 1 && x <= m && y >= 1 && y <= m && !a[x][y])
        return 1;
    return 0;
}
int curba(int x , int y)
{
    if(x > y)
        swap(x , y);
    return min(y - x , x + 8 - y);
}
int dijkstra(int s , int f)
{
    int i , j , x , y , cst , new_cst , d1 , d2;
    for(i = 1 ; i <= n * m ; i ++)
        for(j = 0 ; j < 8 ; j ++)
            d[i][j] = INF;
    priority_queue <car> pq;
    for(i = 0 ; i < 8 ; i ++)
    {
        d[s][i] = 0;
        pq.push(car(s , 0 , i));
    }
    while(!pq.empty())
    {
        x = pq.top().nod;
        cst = pq.top().cost;
        d1 = pq.top().dir;
        pq.pop();
        if(cst > d[x][d1])
            continue;
        for(i = 0 ; i < G[x][d1].size() ; i ++)
        {
            y = G[x][d1][i].nod;
            new_cst = d[x][d1] + G[x][d1][i].cost;
            d2 = G[x][d1][i].dir;
            if(new_cst < d[y][d2])
            {
                d[y][d2] = new_cst;
                pq.push(car(y , new_cst , d2));
            }
        }
    }
    int minim = INF;
    for(i = 0 ; i < 8 ; i ++)
        minim = min(minim , d[f][i]);
    if(minim != INF)
        return minim;
    return -1;
}
int main()
{
    freopen("car.in" , "r" , stdin);
    freopen("car.out" , "w" , stdout);
    int i , j , k , l , xs , ys , xf , yf , x , y , u , v , c , s , f;
    scanf("%d%d%d%d%d%d" , &n , &m , &xs , &ys , &xf , &yf);
    s = (xs - 1) * m + ys;
    f = (xf - 1) * m + yf;
    for(i = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= m ; j ++)
            scanf("%d" , &a[i][j]);
    for(i = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= m ; j ++)
            if(!a[i][j])
            {
                u = m * (i - 1) + j;
                for(k = 0 ; k < 8 ; k ++)
                    for(l = 0 ; l < 8 ; l ++)
                    {
                        x = i + di[l];
                        y = j + dj[l];
                        if(valid(x , y))
                        {
                            v = m * (x - 1) + y;
                            c = curba(k , l);
                            G[u][k].push_back(car(v , c , l));
                        }
                    }
            }
    printf("%d\n" , dijkstra(s , f));
    return 0;
}