Cod sursa(job #2641081)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 9 august 2020 21:38:14
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
const int NMAX = 500;
const short int INF = 32000;
short int di[]= {-1 , -1 , 0 , 1 , 1 , 1 , 0 , -1};
short int dj[]= {0 , 1 , 1 , 1 , 0 , -1 , -1 , -1};
bool a[NMAX + 5][NMAX + 5];
short int d[NMAX * NMAX + 5][9] , n , m;
struct car
{
    short int nod , cost , dir;
    car(short int x = 0 , short int y = 0 , short 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];
short int valid(short int x , short  int y)
{
    if(x >= 1 && x <= m && y >= 1 && y <= m && !a[x][y])
        return 1;
    return 0;
}
short int curba(short int x , short int y)
{
    if(x > y)
        swap(x , y);
    return min(y - x , x + 8 - y);
}
short int dijkstra(short int s , short  int f)
{
    short  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));
            }
        }
    }
    short 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);
    short int i , j , k , l , xs , ys , xf , yf , x , y , u , v , c , s , f;
    scanf("%hd%hd%hd%hd%hd%hd" , &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("%hd" , &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("%hd\n" , dijkstra(s , f));
    return 0;
}