Cod sursa(job #990954)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 29 august 2013 12:51:35
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>

using namespace std;

const int dl[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

const int Nmax = 505;
const int oo = 0x3f3f3f3f;
const int Cmax = 2;

int A[Nmax][Nmax];
int d[ ( 1 << 21 ) ];

stack <int> Coada[Cmax];

int N, M, x1, y1, x2, y2;
int source, destination;

void read()
{
    ifstream f("car.in");

    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],
                    A[i][j] = 1 - A[i][j];

    f.close();
}

inline bool valid( int i, int j )
{
    return A[i][j];
}

inline bool expand( int nod )
{
    int dir = ( nod >> 18 );
    int i = ( nod >> 9 ) & 511;
    int j = nod & 511;

    int son = ( i << 9 ) + j + ( ( ( dir + 1 ) % 8 ) << 18 );

    if ( d[son] > d[nod] + 1 )
    {
        d[son] = d[nod] + 1;
        Coada[ d[son] % 2 ].push( son );
    }

    son = ( i << 9 ) + j + ( ( ( dir - 1 + 8 ) % 8 ) << 18 );

    if ( d[son] > d[nod] + 1 )
    {
        d[son] = d[nod] + 1;
        Coada[ d[son] % 2 ].push( son );
    }

    i += dl[dir];
    j += dc[dir];

    if ( !valid( i, j ) )
            return false;

    if ( i == x2 && j == y2 )
            return true;

    son = ( i << 9 ) + j + ( dir << 18 );

    if ( d[son] > d[nod] )
    {
        d[son] = d[nod];
        Coada[ d[son] % 2 ].push( son );
    }

    return false;
}

int Dijkstra()
{
    memset( d, oo, sizeof( d ) );

    for ( int k = 0; k < 8; ++k )
    {
        int source = ( x1 << 9 ) + y1 + ( k << 18 );

        Coada[0].push( source );
        d[source] = 0;
    }

    int solution = 0;

    while( Coada[0].size() + Coada[1].size() > 0 )
    {
        while( Coada[ solution % 2 ].size() )
        {
            int nod = Coada[ solution % 2 ].top();
            Coada[ solution % 2 ].pop();

            if ( expand( nod ) )
            {
                return solution;
            }
        }

        solution++;
    }

    return -1;
}

void print()
{
    ofstream g("car.out");

    g << Dijkstra() << "\n";

    g.close();
}

int main()
{
    read();
    print();

    return 0;
}