Cod sursa(job #906431)

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

using namespace std;

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


int N, M, X1, Y1, X2, Y2, x, y, t, xn, yn, Min = INF, end;
int A[ MAX_N ][ MAX_N ], B[ MAX_N ][ MAX_N ][8], S[10][10], d[10][2], Q[ MAX_Q ][3];

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])
            ++end, Q[end] = {xn, yn, i}, B[xn][yn][i] = 0;
    }

    for(int q = 1; q <= end; ++q)
    {
        x = Q[q][0], y = Q[q][1], t = Q[q][2];

        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(S[t][i] >= 3)
                continue;
            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], ++end, Q[end] = {xn, yn, i};
        }
    }

    /*for(int k = 0; k < 8; ++k)
        if(B[X2][Y2][k] < Min)
            Min = B[X2][Y2][k];*/
    if(Min != INF)
        g << Min << '\n';
    else g << -1 << '\n';

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

    return 0;
}