Cod sursa(job #1146226)

Utilizator andreiagAndrei Galusca andreiag Data 18 martie 2014 20:15:09
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <fstream>
#include <stack>
#include <string.h>

using namespace std;
const int Nmax = 505;
typedef pair<int, int> pi;
typedef pair<pi, int> ppi;

int bd[Nmax][Nmax];
int dist[8][Nmax][Nmax];
stack<ppi> S[3];

int dx[] = { 0,-1,-1,-1, 0, 1, 1, 1};
int dy[] = { 1, 1, 0,-1,-1,-1, 0, 1};

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

    int N, M, sx, sy, fx, fy;

    f >> N >> M;
    f >> sx >> sy >> fx >> fy;

    for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++)
        f >> bd[i][j];

    memset(dist, -1, sizeof(dist));

    int cur = 0;
    pi start {sx, sy};

    for (int i = 0; i < 8; i++)
    {
        S[cur].push(make_pair(start, i));
        dist[i][start.first][start.second] = 0;
    }

    int answer = -1;
    while (!S[cur].empty())
    {
        bool done = false;
        while (!S[cur].empty())
        {
            ppi pos = S[cur].top(); S[cur].pop();
            int ax = pos.first.first,
                ay = pos.first.second,
                dir = pos.second,
                d = dist[dir][ax][ay];
            if (ax == fx && ay == fy)
            {
                answer = d;
                done = 1; break;
            }
            // move ahead
            int nx = ax + dx[dir],
                ny = ay + dy[dir];
            if (nx > 0 && nx <= N && ny > 0 && ny <= M && !bd[nx][ny]
                && (dist[dir][nx][ny] == -1 || dist[dir][nx][ny] > d))
            {
                dist[dir][nx][ny] = d;
                S[cur].push(make_pair(make_pair(nx, ny), dir));
            }
            // turn 45-deg or 90-deg; left or right;
            for (int sign = -1; sign <= 1; sign += 2)
            for (int delta = 1; delta <= 2; delta++)
            {
                int newdir = (dir + 8 + sign*delta) & 7; // modulo 8
                if (dist[newdir][ax][ay] == -1 || dist[newdir][ax][ay] > d + delta)
                {
                    dist[newdir][ax][ay] = d + delta;
                    S[(cur + delta) % 3].push(make_pair(make_pair(ax, ay), newdir));
                }
            }
        }

        if (done) break;
        else cur = (cur + 1) % 3;
    }

    g << answer << '\n';

    return 0;
}