Cod sursa(job #881273)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 17 februarie 2013 20:56:41
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <fstream>
#include <queue>
#include <cstdlib>

using namespace std;

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

const int nmax= 500, dmax= 8;
const int dx[8]= {0, -1, -1, -1, 0, 1, 1, 1}, 
    dy[8]= {1, 1, 0, -1, -1, -1, 0, 1};

bool u[nmax+2][nmax+2][dmax];

inline int enc(int x, int y, int d){
    return ((x<<12)+(y<<3)+d);
}

queue <int> q[2];

char *buffer;

void read_int(int &x){
    while (*buffer<'0'|| *buffer>'9'){
        ++buffer;
    }
    x= 0;
    while (*buffer>='0'&& *buffer<='9'){
        x= 10*x+*buffer-'0';
        ++buffer;
    }
}

void read_bool(bool &x){
    while (*buffer!='0'&& *buffer!='1'){
        ++buffer;
    }
    x= *buffer-'0';
    ++buffer;
}

int main()
{
    fin.seekg(0, ios::end);
    int fs= fin.tellg();
    fin.seekg(0, ios::beg);
    buffer= (char*)malloc(fs);
    fin.getline(buffer, fs, 0);

    int n, m;
    read_int(n); read_int(m);
    int src_x, src_y, dest_x, dest_y;
    read_int(src_x); read_int(src_y); 
    read_int(dest_x); read_int(dest_y);
    for (int i= 1; i<=n; ++i){
        for (int j= 1; j<=m; ++j){
            read_bool(u[i][j][0]);
            if (u[i][j][0]){
                for (int k= 1; k<dmax; ++k){
                    u[i][j][k]= 1;
                }
            }
        }
    }
    for (int i= 0; i<dmax; ++i){
        for (int j= 0; j<=n+1; ++j){
            u[j][0][i]= 1;
            u[j][m+1][i]= 1;
        }
        for (int j= 1; j<=m; ++j){
            u[0][j][i]= 1;
            u[n+1][j][i]= 1;
        }
    }

    for (int i= 0; i<dmax; ++i){
        q[0].push(enc(src_x, src_y, i));
    }
    for (int i= 0; !(q[0].empty()&& q[1].empty()); ++i){
        int ind= i&1, indp= (i+1)&1;
        while (q[ind].empty()==0){
            int aux= q[ind].front();
            int x= aux>>12, y= (aux>>3)&511, d= aux&7;
            if (x==dest_x&& y==dest_y){
                fout<<i<<"\n";
                return 0;
            }
            
            q[ind].pop();
            if (u[x][y][d]==0){
                u[x][y][d]= 1;
                if (u[x+dx[d]][y+dy[d]][d]==0){
                    q[ind].push(enc(x+dx[d], y+dy[d], d));
                }
                for (int j= (d+7)&7; j!=((d+3)&7); j= (j+2)&7){
                    if (u[x][y][j]==0){
                        q[indp].push(enc(x, y, j));
                    }
                }
            }
        }
    }
    fout<<"-1\n";

    return 0;
}