Cod sursa(job #1159977)

Utilizator mihai995mihai995 mihai995 Data 30 martie 2014 00:00:52
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 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 use[1 << 21], bad[N][N];
priority_queue<Per> Q;

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

inline int cod(int x, int y, int dir){
    return (x << 11) ^ (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 << 11) * 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 expand(int y, int c){
    if (c < dist[y]){
        dist[y] = c;
        Q.push( Per(y, c) );
    }
}

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 x = cod(startX, startY, 0), dest = cod(endX, endY, 0) >> 3;
    for (int i = 0 ; i < nrDir ; i++)
        Q.push( Per(x + i, 0) );

    ///DIJKSTRA PROPRIU-ZIS
    while (!Q.empty()){
        x = Q.top().node; Q.pop();
        if ( use[x] )
            continue;
        use[x] = true;

        if ( (x >> 3) == dest )
            return dist[x];

        expand( rotLeft(x), dist[x] + 1 );
        expand( rotRight(x), dist[x] + 1 );
        expand( vecin(x), dist[x] );
    }

    return -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;
}