Cod sursa(job #2641071)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 9 august 2020 20:22:55
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <cstdio>
#include <queue>
#include <algorithm>
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 + 5][NMAX + 5][9] , n , m , xs , ys , xf , yf;
struct car
{
    int x , y , z , d;
    car(int tx = 0 , int ty = 0 , int tz = 0 , int td = 0)
    {
        x = tx;
        y = ty;
        z = tz;
        d = td;
    }
};
bool operator>(const car& a , const car& b)
{
  return a.d < b.d;
}
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 lee()
{
    int i , j , k , x1 , y1 , z1 , d1 , x2 , y2 , cst;
    for(i = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= m ; j ++)
            for(k = 0 ; k < 8 ; k ++)
                d[i][j][k] = INF;
    queue <car> q;
    for(k = 0 ; k < 8 ; k ++)
    {
        d[xs][ys][k] = 0;
        q.push(car(xs , ys , k , 0));
    }
    while(!q.empty())
    {
        x1 = q.front().x;
        y1 = q.front().y;
        z1 = q.front().z;
        d1 = q.front().d;
        q.pop();
        if(d[x1][y1][z1] < d1)
          continue;
        for(i = 0 ; i < 8 ; i ++)
        {
            x2 = x1 + di[i];
            y2 = y1 + dj[i];
            cst = curba(z1 , i);
            if(valid(x2 , y2) && d[x2][y2][i] > d[x1][y1][z1] + cst)
            {
                d[x2][y2][i] = d[x1][y1][z1] + cst;
                q.push(car(x2 , y2 , i , d[x2][y2][i]));
            }
        }
    }
    int minim = INF;
    for(i = 0 ; i < 8 ; i ++)
        minim = min(minim , d[xf][yf][i]);
    if(minim != INF)
        return minim;
    return -1;
}
int main()
{
    freopen("car.in" , "r" , stdin);
    freopen("car.out" , "w" , stdout);
    int i , j;
    scanf("%d%d%d%d%d%d" , &n , &m , &xs , &ys , &xf , &yf);
    for(i = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= m ; j ++)
            scanf("%d" , &a[i][j]);
    printf("%d\n" , lee());
    return 0;
}