Cod sursa(job #2641090)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 10 august 2020 00:11:27
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 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;
    car(int tx = 0 , int ty = 0 , int tz = 0)
    {
        x = tx;
        y = ty;
        z = tz;
    }
};
int valid(int x , int y)
{
    if(x >= 1 && x <= m && y >= 1 && y <= m && !a[x][y])
        return 1;
    return 0;
}
int lee()
{
    int i , j , k , x1 , y1 , z1 , x2 , y2 , z2;
    for(i = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= m ; j ++)
            for(k = 0 ; k < 8 ; k ++)
                d[i][j][k] = INF;
    deque <car> q;
    for(k = 0 ; k < 8 ; k ++)
    {
        d[xs][ys][k] = 0;
        q.push_back(car(xs , ys , k));
    }
    while(!q.empty())
    {
        x1 = q.front().x;
        y1 = q.front().y;
        z1 = q.front().z;
        q.pop_front();
        if(x1 == xf && y1 == yf)
            return d[x1][y1][z1];
        x2 = x1 + di[z1];
        y2 = y1 + dj[z1];
        if(valid(x2 , y2) && d[x2][y2][z1] > d[x1][y1][z1])
        {
            d[x2][y2][z1] = d[x1][y1][z1];
            q.push_front(car(x2 , y2 , z1));
        }
        for(i = 1 ; i <= 4 ; i ++)
        {
            z2 = (z1 + i) % 8;
            x2 = x1 + di[z2];
            y2 = y1 + dj[z2];
            if(valid(x2 , y2) && d[x2][y2][z2] > d[x1][y1][z1] + i)
            {
                d[x2][y2][z2] = d[x1][y1][z1] + i;
                q.push_back(car(x2 , y2 , z2));
            }
            z2 = (z1 - i + 8) % 8;
            x2 = x1 + di[z2];
            y2 = y1 + dj[z2];
            if(valid(x2 , y2) && d[x2][y2][z2] > d[x1][y1][z1] + i)
            {
                d[x2][y2][z2] = d[x1][y1][z1] + i;
                q.push_back(car(x2 , y2 , z2));
            }
        }
    }
    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;
}