Cod sursa(job #906402)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 6 martie 2013 20:08:10
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

const int MAX_N = 505;
const int INF = 0x3f3f3f3f;

typedef struct
{
    int x, y, t;
} stare;

int N, M, X1, Y1, X2, Y2, x, y, t, xn, yn, Min = INF;
int A[ MAX_N ][ MAX_N ], B[ MAX_N ][ MAX_N ][8], S[10][10], d[10][2];
stare P;
queue < stare > Q;

int main()
{
    ifstream f("car.in");
    ofstream g("car.out");

    f >> N >> M >> X1 >> Y1 >> X2 >> Y2;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            f >> A[i][j];

    d[0] = {1, 0};
    d[1] = {1, 1};
    d[2] = {0, 1};
    d[3] = {-1, 1};
    d[4] = {-1, 0};
    d[5] = {-1, -1};
    d[6] = {0, -1};
    d[7] = {1, -1};

    S[0] = {0, 1, 2, 3, 4, 3, 2, 1};
    for(int i = 1; i < 8; ++i)
    {
        int j = -1;
        for(int k = 7 - i + 1; k <= 7; ++k)
            ++j, S[i][j] = S[0][k];
        for(int k = 0; k < 7 - i + 1; ++k)
            ++j, S[i][j] = S[0][k];
    }

    for(int i = 0; i <= N + 1; ++i)
        A[i][0] = A[i][M+1] = 1;
    for(int j = 0; j <= M + 1; ++j)
        A[0][j] = A[N+1][j] = 1;
    memset(B, INF, sizeof(B));

    for(int i = 0; i < 8; ++i)
    {
        xn = X1 + d[i][0], yn = Y1 + d[i][1];
        if(!A[xn][yn])
            P.x = xn, P.y = yn, P.t = i, Q.push(P), B[xn][yn][i] = 0;
    }

    while(!Q.empty())
    {
        P = Q.front();
        Q.pop();

        x = P.x, y = P.y, t = P.t;
        if(x == X2 && y == Y2)
        {
            if(B[x][y][t] < Min)
                Min = B[x][y][t];
            continue;
        }
        if(B[x][y][t] >= Min)
            continue;
        for(int i = 0; i < 8; ++i)
        {
            xn = x + d[i][0], yn = y + d[i][1];

            if(!A[xn][yn] && B[x][y][t] + S[t][i] < B[xn][yn][i])
                B[xn][yn][i] = B[x][y][t] + S[t][i], P.x = xn, P.y = yn, P.t = i, Q.push(P);
        }
    }

    if(Min != INF)
        g << Min << '\n';
    else g << -1 << '\n';

    f.close();
    g.close();

    return 0;
}