Cod sursa(job #1906973)

Utilizator FlowstaticBejan Irina Flowstatic Data 6 martie 2017 17:14:21
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <fstream>
#include <queue>
#define NMAX 560
#define INF 1<<30
#define FOR(i,a,b) for(int i= a; i<=b;i++)
using namespace std;

int N,M;
int xs,ys,xf,yf;

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

int best[NMAX][NMAX][8];
int a[NMAX][NMAX];

struct Node
{
    int x,y,dir;
    Node(int x = 0, int y = 0, int dir = 0) : x(x), y(y), dir(dir) {}
    bool operator() (Node a, Node b)
    {
        return best[a.x][a.y][a.dir] > best[b.x][b.y][b.dir];
    }
};

queue<Node> Q;
vector<queue<Node> > vs;

int Solve();

int main()
{
    ifstream fin("car.in");
    fin>>N>>M;
    fin>>xs>>ys>>xf>>yf;
    FOR(i,1,N)
        FOR(j,1,M)
            fin>>a[i][j];
    fin.close();

    FOR(i,0,N+1)
        a[i][0] = a[i][M+1] = 1;
    FOR(j,0,M+1)
        a[0][j] = a[N+1][j] = 1;

    FOR(i,0,N)
        FOR(j,1,M)
            FOR(d,0,7)
                best[i][j][d] = INF;

    ofstream fout("car.out");
    fout<<Solve()<<'\n';
    fout.close();

    return 0;
}

int Solve()
{
    vs.push_back(Q);
    vs.push_back(Q);

    FOR(d,0,7)
    {
        int nx = xs + dx[d];
        int ny = ys + dy[d];

        if(!a[nx][ny])
        {
            vs[0].push(Node(nx,ny,d));
            best[nx][ny][d] = 0;
        }
    }

    while(!vs[0].empty())
    {
        Node nod = vs[0].front();
        vs[0].pop();

        if(nod.x == xf && nod.y == yf)
            return best[nod.x][nod.y][nod.dir];

        FOR(i, nod.dir-1, nod.dir +1)
        {
            int d = i;
            if(d == -1)
                d = 7;
            else if(d == 8)
                d = 0;

            int nx = nod.x + dx[d];
            int ny = nod.y + dy[d];
            int cost = abs(nod.dir - i);
            if(!cost && !a[nx][ny] && best[nod.x][nod.y][nod.dir] + cost < best[nx][ny][d])
            {
                best[nx][ny][d] = best[nod.x][nod.y][nod.dir] + cost;
                vs[cost].push(Node(nx,ny,d));
            }

            if(cost && best[nod.x][nod.y][nod.dir] + cost < best[nod.x][nod.y][d])
            {
                best[nod.x][nod.y][d] = best[nod.x][nod.y][nod.dir] + cost;
                vs[cost].push(Node(nod.x,nod.y,d));
            }
        }
        if(vs[0].empty())
        {
            swap(vs[0],vs[1]);
            vs[1] = Q;
        }
    }
    return -1;
}