Cod sursa(job #2641091)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 10 august 2020 00:26:10
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 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> dq;
    for(k = 0 ; k < 8 ; k ++)
    {
        d[xs][ys][k] = 0;
        dq.push_back(car(xs , ys , k));
    }
    while(!dq.empty())
    {
        x1 = dq.front().x;
        y1 = dq.front().y;
        z1 = dq.front().z;
        dq.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];
            dq.push_front(car(x2 , y2 , z1));
        }
        z2 = (z1 + 1) % 8;
        if(d[x1][y1][z2] > d[x1][y1][z1] + 1)
        {
            d[x1][y1][z2] = d[x1][y1][z1] + 1;
            dq.push_back(car(x1 , y1 , z2));
        }
        z2 = (z1 - 1 + 8) % 8;
        if(d[x1][y1][z2] > d[x1][y1][z1] + i)
        {
            d[x1][y1][z2] = d[x1][y1][z1] + 1;
            dq.push_back(car(x1 , y1 , 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;
}