Cod sursa(job #1096081)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 1 februarie 2014 15:12:01
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <cstring>
#define NMax 512
#define MMax 512

using namespace std;

const int INF = 0x3f3f3f3f;
bool foundSol = false;
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, m;
int a[NMax][MMax], dist[8][NMax][MMax];
struct stare
{
    int x, y, dir;
    stare() {}
    stare(const int _x, const int _y, const int _dir)
    {
        x = _x, y = _y, dir = _dir;
    }
};
queue <stare> Q[2];
int xs, ys, xf, yf;

void Read()
{
    ifstream f("car.in");
    f>>n>>m>>xs>>ys>>xf>>yf;
    for (int i = 1; i<=n; ++i)
        for (int j = 1; j<=m; ++j)
            f>>a[i][j];
    f.close();
}

void Bordare()
{
    int n1 = n + 1, m1 = m + 1;
    for (int i = 0; i<=n1; ++i)
        a[i][0] = a[i][m1] = 1;
    for (int i = 0; i<=m1; ++i)
        a[0][i] = a[n1][i] = 1;
}

void Solve()
{
    Bordare();
    memset(dist, INF, sizeof(dist));
    for (int i = 0 ; i < 8 ; ++i)
    {
        dist[i][xs][ys] = 0;
        Q[0].push(stare(xs, ys, i));
    }
    int p = 0;
    while (!Q[p].empty())
    {
        while (!Q[p].empty())
        {
            stare aux = Q[p].front(); Q[p].pop();
            if (aux.x == xf && aux.y == yf)
            {
                ofstream g("car.out");
                g<<dist[aux.dir][xf][yf]<<"\n";
                g.close();
                foundSol = true;
                return ;
            }
            int nowdir = aux.dir, nextdir, cost;

            /// ma duc mai departe pe aceeasi directie cu cost 0
            cost = 0; nextdir = nowdir;
            if (a[aux.x + dx[nextdir]][aux.y + dy[nextdir]] == 0 && dist[nowdir][aux.x][aux.y] + cost < dist[nextdir][aux.x + dx[nextdir]][aux.y + dy[nextdir]])
            {
                dist[nextdir][aux.x + dx[nextdir]][aux.y + dy[nextdir]] = dist[nowdir][aux.x][aux.y] + cost;
                Q[p].push(stare(aux.x + dx[nextdir], aux.y + dy[nextdir], nextdir));
            }

            /// raman aici dar schimb directia la 45 de grade intr-o parte cu cost 1
            cost = 1, nextdir = nowdir + 1 >= 8 ? nowdir + 1 - 8 : nowdir + 1;
            if (a[aux.x][aux.y] == 0 && dist[nowdir][aux.x][aux.y] + cost < dist[nextdir][aux.x][aux.y])
            {
                dist[nextdir][aux.x][aux.y] = dist[nowdir][aux.x][aux.y] + cost;
                Q[1-p].push(stare(aux.x, aux.y, nextdir));
            }

            /// raman aici dar schimb directia la 45 de grade in partea cealalta cu cost 1
            cost = 1, nextdir = nowdir - 1 < 0 ? nowdir - 1 + 8 : nowdir - 1;
            if (a[aux.x][aux.y] == 0 && dist[nowdir][aux.x][aux.y] + cost < dist[nextdir][aux.x][aux.y])
            {
                dist[nextdir][aux.x][aux.y] = dist[nowdir][aux.x][aux.y] + cost;
                Q[1-p].push(stare(aux.x, aux.y, nextdir));
            }
        }
        p = 1 - p;
    }
}

int main()
{
    Read();
    Solve();
    if (!foundSol)
    {
        ofstream g("car.out");
        g<<"-1\n";
        g.close();
    }
    return 0;
}