Cod sursa(job #1159989)

Utilizator mihai995mihai995 mihai995 Data 30 martie 2014 00:26:53
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 501, nrDir = 8, inf = 0x3f3f3f3f;
const int dl[] = {-1, -1, 0, 1, 1,  1,  0, -1};
const int dc[] = { 0,  1, 1, 1, 0, -1, -1, -1};

struct Per{
    int node, value;
    Per(int node, int value) : node(node), value(value) {};

    inline bool operator<(const Per& P) const {
        return value > P.value;
    }
};

int dist[1 << 21], n, m;
bool bad[N][N];
int list[2][1 << 21];

ifstream in("car.in");
ofstream out("car.out");

inline int cod(int x, int y, int dir){
    return (x << 12) ^ (y << 3) ^ dir;
}

inline int rotLeft(int C){
    return ( (C & 7) != 7 ) ? C + 1 : (C ^ 7);
}

inline int rotRight(int C){
    return ( (C & 7) != 0 ) ? C - 1 : (C ^ 7);
}

inline int vecin(int C){
    return C + (1 << 12) * dl[C & 7] + (1 << 3) * dc[C & 7];
}

inline void markDist(int x, int y, int val){
    int p = cod(x, y, 0);
    for (int i = 0 ; i < nrDir ; i++)
        dist[ p + i ] = val;
}

inline void push(int v[], int x){
    v[ ++v[0] ] = x;
}

int dijkstra(int startX, int startY, int endX, int endY){
    memset(dist, inf, sizeof(dist));

    ///INITIALIZARE
    markDist(startX, startY, 0);
    for (int i = 0 ; i <= n + 1 ; i++){
        markDist(i, 0, 0);
        markDist(i, m + 1, 0);
    }
    for (int i = 0 ; i <= m + 1 ; i++){
        markDist(0, i, 0);
        markDist(n + 1, i, 0);
    }
    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= m ; j++)
            if ( bad[i][j] )
                markDist(i, j, 0);

    ///INTRODUCERE IN HEAP
    int act = 0;
    int x = cod(startX, startY, 0), y;
    for (int i = 0 ; i < nrDir ; i++)
        push(list[act], x + i);

    ///DIJKSTRA PROPRIU-ZIS
    while ( list[act][0] ){
        for (int i = 1 ; i <= list[act][0] ; i++){
            x = list[act][i];
            y = vecin(x);
            if ( dist[y] == inf ){
                dist[y] = dist[x];
                push(list[act], y);
            }
        }
        for (int i = 1 ; i <= list[act][0] ; i++){
            x = list[act][i];
            y = rotLeft(x);
            if ( dist[y] == inf ){
                dist[y] = dist[x] + 1;
                push(list[act ^ 1], y);
            }
            y = rotRight(x);
            if ( dist[y] == inf ){
                dist[y] = dist[x] + 1;
                push(list[act ^ 1], y);
            }
        }
        list[act][0] = 0;
        act ^= 1;
    }
    ///EXTRACT RESULT
    int best = inf, dest = cod(endX, endY, 0);
    for (int i = 0 ; i < nrDir ; i++)
        if (dist[ dest + i ] < best)
            best = dist[ dest + i ];
    return best != inf ? best : -1;
}

int main(){
    int startX, startY, endX, endY;

    in >> n >> m;
    in >> startX >> startY >> endX >> endY;
    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= m ; j++)
            in >> bad[i][j];

    out << dijkstra(startX, startY, endX, endY) << '\n';
    return 0;
}