Cod sursa(job #893673)

Utilizator darrenRares Buhai darren Data 26 februarie 2013 17:09:43
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <algorithm>
#include <deque>

using namespace std;

const int D1[] = {-1, -1, 0, 1, 1, 1, 0, -1},
          D2[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int INF = 0x3f3f3f3f;

int N, M, Si, Sj, Fi, Fj;
int A[502][502];
int minC[502][502][8];
deque<pair<pair<int, int>, int> > Q;

inline bool ok(int x, int y)
{
    return x >= 1 && y >= 1 && x <= N && y <= M && !A[x][y];
}

int main()
{
    ifstream fin("car.in");
    ofstream fout("car.out");

    fin >> N >> M;
    fin >> Si >> Sj >> Fi >> Fj;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
        {
            fin >> A[i][j];
            for (int k = 0; k < 8; ++k)
                minC[i][j][k] = INF;
        }
    for (int k = 0; k < 8; ++k)
    {
        minC[Si][Sj][k] = 0;
        Q.push_back(make_pair(make_pair(Si, Sj), k));
    }

    while (!Q.empty())
    {
        pair<int, int> now = Q.front().first;
        int dir = Q.front().second;

        Q.pop_front();

        if (ok(now.first + D1[dir], now.second + D2[dir]) && minC[now.first][now.second][dir] < minC[now.first + D1[dir]][now.second + D2[dir]][dir])
        {
            Q.push_front(make_pair(make_pair(now.first + D1[dir], now.second + D2[dir]), dir));
            minC[now.first + D1[dir]][now.second + D2[dir]][dir] = minC[now.first][now.second][dir];
        }

        int next1 = ((dir + 8) - 1) % 8, next2 = ((dir + 8) + 1) % 8;
        if (minC[now.first][now.second][dir] + 1 < minC[now.first][now.second][next1])
        {
            if (minC[now.first][now.second][next1] == INF) Q.push_back(make_pair(now, next1));
            minC[now.first][now.second][next1] = minC[now.first][now.second][dir] + 1;
        }
        if (minC[now.first][now.second][dir] + 1 < minC[now.first][now.second][next2])
        {
            if (minC[now.first][now.second][next2] == INF) Q.push_back(make_pair(now, next2));
            minC[now.first][now.second][next2] = minC[now.first][now.second][dir] + 1;
        }
    }

    int result = INF;
    for (int k = 0; k < 8; ++k)
        result = min(result, minC[Fi][Fj][k]);

    if (result == INF) result = -1;
    fout << result << '\n';

    fin.close();
    fout.close();
}