Cod sursa(job #1701610)

Utilizator Athena99Anghel Anca Athena99 Data 13 mai 2016 17:46:22
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int inf= 1<<30;
const int nmax= 500;
const int dx[]= {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[]= {0, 1, 1, 1, 0, -1, -1, -1};

int n, m, x1, y1, x2, y2, sol= -1;
int v[nmax+1][nmax+1], d[nmax+1][nmax+1][8];

queue <int> q[2];

int val( int i, int j, int d ) {
    return (i<<9)+j+(d<<18);
}

int fd( int x ) {
    return (x>>18);
}

int fx( int x ) {
    return ((x>>9)&511);
}

int fy( int x ) {
    return (x&511);
}

void add( int x, int y, int dir, int nr, int k ) {
    if ( d[x][y][dir]>nr ) {
        d[x][y][dir]= nr;
        q[k].push(val(x, y, dir));
    }
}

int main(  ) {
    fin>>n>>m>>x1>>y1>>x2>>y2;
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            fin>>v[i][j];
            for ( int k= 0; k<8; ++k ) {
                d[i][j][k]= inf;
            }
        }
    }

    for ( int i= 0; i<8; ++i ) {
        q[0].push(val(x1, y1, i));
        d[x1][y1][i]= 0;
    }
    for ( int cnt= 0, k= 0; (!q[0].empty() || !q[1].empty()) && sol==-1; ++cnt, k^= 1 ) {
        for ( int x, y, dir, a, b; !q[k].empty() && sol==-1; q[k].pop() ) {
            x= fx(q[k].front()), y= fy(q[k].front()), dir= fd(q[k].front()); a= x+dx[dir], b= y+dy[dir];
            if ( x==x2 && y==y2 ) {
                sol= cnt;
            }

            if ( a>=1 && a<=n && b>=1 && b<=m && v[a][b]==0 && d[a][b][dir]>cnt ) {
                d[a][b][dir]= cnt;
                q[k].push(val(a, b, dir));
            }

            add(x, y, (dir+1)%8, cnt+1, k^1);
            add(x, y, (dir+7)%8, cnt+1, k^1);
        }
    }

    fout<<sol<<"\n";

    return 0;
}