Cod sursa(job #841189)

Utilizator stoicatheoFlirk Navok stoicatheo Data 23 decembrie 2012 21:26:18
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>
#include <queue>
using std::queue;
 
#define MAXN 500
#define dirMask 7
#define yMask 4088
 
bool mat[MAXN][MAXN];
 
const int delta[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
int dist[MAXN][MAXN][8];
queue<int> Q[2];
 
int sx, sy, fx, fy, n, m, result;
 
inline int getCode(int x, int y, int dir)
{
    return (x << 12) + (y << 3) + dir;
}
 
inline bool withinBounds(int x, int y)
{
    return x >= 0 && x < n && y >= 0 && y < m;
}
 
inline void relax(int state, int crtList)
{
    int x = state >> 12;
    int y = (state & yMask) >> 3;
    int dir = state & dirMask;
 
    if (x == fx && y == fy)
    {
        result = dist[x][y][dir] + 1;
        return;
    }
 
    int crtDir = dir;
    int newX = x + delta[crtDir][0], newY = y + delta[crtDir][1];
    if (withinBounds(newX, newY) && mat[newX][newY] == 0 && (dist[newX][newY][crtDir] > dist[x][y][dir]))
    {
        dist[newX][newY][crtDir] = dist[x][y][dir];
        Q[crtList].push(getCode(newX, newY, crtDir));
    }
 
    crtDir = dir + 1 > 7 ? 0 : dir + 1;
    if (dist[x][y][crtDir] > dist[x][y][dir] + 1)
    {
        dist[x][y][crtDir] = dist[x][y][dir] + 1;
        Q[1 - crtList].push(getCode(x, y, crtDir));
    }
 
    crtDir = dir - 1 < 0 ? 7 : dir - 1;
    if (dist[x][y][crtDir] > dist[x][y][dir] + 1)
    {
        dist[x][y][crtDir] = dist[x][y][dir] + 1;
        Q[1 - crtList].push(getCode(x, y, crtDir));
    }
}
 
int main()
{
    freopen("car.in", "r", stdin);
    freopen("car.out","w",stdout);
    scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &fx, &fy);
 
    sx--;sy--;fx--;fy--;
 
    for (int i = 0 ; i < n ; ++i)
        for (int j = 0 ; j < m ; ++j)
        {
            scanf("%d", &mat[i][j]);
            if (mat[i][j] == 0)
                for (int k = 0 ; k < 8 ; ++k)
                    dist[i][j][k] = 0x7fffffff;
        }
 
    for (int i = 0 ; i < 8 ; ++i)
    {
        Q[0].push(getCode(sx, sy, i));
        dist[sx][sy][i] = 0;
    }
 
    int current_cost = 0, pos = 0, crt = 0;
 
    while ((!Q[0].empty() || !Q[1].empty()) && result < 1)
    {
        while (!Q[crt].empty() && result < 1)
        {
            int crtElem = Q[crt].front();
            Q[crt].pop();
            relax(crtElem, crt);
        }
 
        crt = 1 - crt;
    }
 
    printf("%d\n", result - 1);
 
    return 0;
}