Cod sursa(job #288396)

Utilizator flamecataCiobanu Alexandru-Catalin flamecata Data 25 martie 2009 19:19:49
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 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;   
}