Cod sursa(job #1105677)

Utilizator gbi250Gabriela Moldovan gbi250 Data 11 februarie 2014 23:19:14
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <cstdio>
#include <queue>
#include <cstring>

#define SIZE 512
#define SIZE_dist (1<<21)

using namespace std;

int n, m, Xi, Yi, Xf, Yf, cost_min;
int sol[SIZE][SIZE], adj[SIZE][SIZE], dist[SIZE_dist];
bool ok_path;
queue <int> q[ 2 ];

inline void read();
inline void solve();
inline void write();

int main()
{
    read();
    solve();
    write();
    return 0;
}

inline void read()
{
    freopen("car.in", "r", stdin);
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &Xi, &Yi, &Xf, &Yf);
    for(int i = 1; i <= n; ++i)
        for(int j = 1;j <= m; ++j)
            scanf("%d", &adj[i][j]);
}

inline int encode( int X, int Y, int dir )
{
    return  ( ( (X - 1) * m + Y - 1 ) * 8 + dir);
}

inline void expand(int node)
{
    int dir, node_next, node_tmp, x, y;

    node_tmp = node;

    dir = node_tmp % 8; node_tmp /= 8;
    y = node_tmp % m + 1;
    x = node_tmp / m + 1;

    node_next = encode( x, y,  ( dir + 1 ) % 8); // +45 de grade (sensul invers trigonometric)

    if( dist[ node_next ] > dist[ node ] + 1 )
    {
        dist[ node_next ] = dist[ node ] + 1;
        q[ dist[node_next] & 1 ].push( node_next );
    }

    node_next = encode( x, y, ( dir + 7 ) % 8); // -45 de grade (sensul trigonometric)

    if( dist[ node_next ] > dist[ node ] + 1 )
    {
        dist[ node_next ] = dist[ node ] + 1;
        q[ dist[node_next] & 1].push( node_next );
    }

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


    x += dl[ dir ];
    y += dc[ dir ];

    if( x > n || x < 1 || y > m || y < 1 || adj[ x ][ y ] )
        return ;
    if( x == Xf && y == Yf)
    {
        ok_path = 1;
        return ;
    }

    int node_same_dir = encode( x, y, dir);

    if( dist[ node_same_dir ] > dist[ node ])
    {
        dist[ node_same_dir ] = dist[ node ];

        q[ dist[ node_same_dir ] & 1 ].push( node_same_dir );
    }
}

inline void solve()
{
    memset( dist, 0x3f, sizeof(dist) );

    int node;

    for(int i = 0; i < 8; ++i)
    {
        node = encode(Xi, Yi, i);
        q[0].push( node ); // din pozitia initiala putem ajunge in nodul codat node pana la care am folosit costul 0
        dist[ node ] = 0;
    }

    while( ( !q[0].empty() || !q[1].empty() ) && !ok_path)
    {

        while( !q[ cost_min & 1 ].empty() && !ok_path)
        {
            node = q[ cost_min & 1].front();

            q[ cost_min & 1].pop();

            expand( node );
        }
        if( ok_path )
            return ;
        ++cost_min;
    }
}


inline void write()
{
    freopen("car.out", "w", stdout);
    if( ok_path )
        printf("%d\n", cost_min);
    else
        printf("-1\n");
}