Cod sursa(job #1042030)

Utilizator ericptsStavarache Petru Eric ericpts Data 26 noiembrie 2013 15:01:21
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <fstream>
#include <queue>
#include <utility>
#include <cstring>
#include <cctype>


using namespace std;

const short MAX_N = 505;

const short dx[] = {1,1,0,-1,-1,-1, 0, 1};
const short dy[] = {0,1,1, 1, 0,-1,-1,-1};

int bst[1 << 21];
bool viz[1 << 21];
bool bad[MAX_N * MAX_N];

struct state{
    int info;

    short x(){
        return info % (1 << 9);
    }

    short y(){
        return (info >> 9) % (1 << 9);
    }

    short dir(){
        return (info >> 18);
    }

    state(short x, short y, short from):
        info( (from << 18) + (y << 9) + x ){}

    state():
        info(0){}
};

queue<state> Qi[2];

ofstream out("car.out");

short n,m;
short x0,y0;
short x1,y1;

inline bool inside(state now){
    return now.x() >= 1 && now.x() <= n && now.y() >= 1 && now.y() <= m && !bad[now.x() + (now.y() << 9)];
}

inline void add(const state prev, const state now, queue<state> &Q, const short cst){
    if(!inside(now))
        return;
    if(bst[prev.info] + cst < bst[now.info] || !viz[now.info]){
        viz[now.info] = 1;
        bst[now.info] = bst[prev.info] + cst;
        Q.push(now);
    }
}

short chg[] = {0,1,-1};

int spread(){

    memset(bst, 0x3f, sizeof(bst));
    state now;

    for(int i = 0 ; i < 8 ; ++i){
        now = state( x0, y0, i );

        viz[ now.info] = 1;
        Qi[0].push( now );
    }

    for(int dst = 0 ; !Qi[0].empty() || !Qi[1].empty() ; ++dst){
        bool const cr = dst % 2;
        queue<state> &Q = Qi[cr];

        while(!Q.empty()) {

            now = Q.front();

            Q.pop();

            const short x = now.x(),
                      y = now.y(),
                      dir = now.dir();

            if(x == x1 && y == y1)
                return dst;

            for(short i = 0 ; i < 3 ; ++i){
                short const ndir = (dir + chg[i] + 8) % 8;

                add(now, state(x + dx[ndir] * (ndir == dir), y + dy[ndir] * (ndir == dir), ndir), Qi[(dst + (i > 0)) % 2], i > 0);
            }
        }
    }

    return -1;
}




struct parser{

    parser():
        DIM(1 << 14)
        {
        freopen("car.in", "r", stdin);}

    const short DIM;
    char buff[1 << 14];

    char next_char(){
        static short at = DIM - 1;
        ++at;
        if(at == DIM){
            fread(buff, 1, DIM, stdin);
            at = 0;
        }
        return buff[at];
    }

    short next_int(){
        char now;

        do{
            now = next_char();
        }while(!isdigit(now));

        short ret = 0;

        do{
            ret = ret * 10 + now - '0';
            now = next_char();
        }while(isdigit(now));

        return ret;
    }
    template<class T>
    void operator>> (T &val){
        val = next_int();
    }
}in;

int main(){
    in >> n;
    in >> m;
    in >> x0;
    in >> y0;
    in >> x1;
    in >> y1;

    for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= m ; ++j)
        in >> bad[i + (j << 9)];

    out << spread() << "\n";

    return 0;
}