Cod sursa(job #286654)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 23 martie 2009 23:33:27
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <queue>
#include <bitset>
using namespace std;
int N,M,xi,yi,xf,yf;
bitset<512> a[512];
queue<int> L[2];
const int Inf=2000000000;
const int dx[8]={0,-1,-1,-1, 0,+1,1,1};
const int dy[8]={1,+1, 0,-1,-1,-1,0,1};
int d[8][512][512];
int main(){
    int i,j,k;
    ifstream f("car.in");
    ofstream g("car.out");
    f>>N>>M;
    f>>xi>>yi>>xf>>yf;
    for (i=1;i<=N;++i)
     for (j=1;j<=M;++j)
      f>>k,a[i][j]=k;
    memset(d,0x3f,sizeof(d));
    k=0;
    for (i=0;i<8;++i){
      L[k].push(xi + (yi<<9) + (i<<18));
      d[i][xi][yi]=0;
      }
    int dir,x,y,_x,_y,_dir,now=0;
    for (;L[0].size()+L[1].size()>0;++k){
          now=k&1;
          for (;!L[now].empty();L[now].pop()){
                i=L[now].front();
                dir=i>>18;
                x=i&511;
                y=(i>>9)&511;
                if (x==xf && y==yf ) {g<<k;
                                      return 0;}
                _x=x+dx[dir];
                _y=y+dy[dir];
                if (_x>0 && _x<=N && _y>0 && _y<=M && !a[_x][_y])
                  if (d[dir][_x][_y]>k){
                    d[dir][_x][_y]=k;
                    L[now].push(_x + (_y<<9) + (dir<<18));
                    }
                    
                _dir=(dir+1)%8;
                if (d[_dir][x][y]>k+1){
                      d[_dir][x][y]=k+1;
                      L[(now+1)&1].push(x+ (y<<9) + (_dir<<18));
                                      }
                _dir=(dir+7)%8;
                if (d[_dir][x][y]>k+1){
                      d[_dir][x][y]=k+1;
                      L[(now+1)&1].push(x+ (y<<9) + (_dir<<18));
                                      }                                         
                }
          }
    g<<-1;     
    return 0;
}