Cod sursa(job #286540)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 23 martie 2009 21:34:24
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <list>
#include <bitset>
using namespace std;
int N,M,xi,yi,xf,yf;
bitset<512> a[512];
list<int> L[3];
const int Inf=2000000000;
const int dx[8][5]={{0,-1,-1,1,1},{-1,-1,-1,0,1},{-1,-1, 0,-1,0},{-1, 0,+1,-1,-1},
                    { 0,+1,1,-1,-1},{+1,1,1, 0,-1},{1,1,0,+1, 0},{1,0,-1,1,+1}};
const int dy[8][5]={{1,+1, 0,1,0},{+1, 0,-1,1,1},{ 0,-1,-1,+1,1},{-1,-1,-1, 0,+1},
                    {-1,-1,0,-1, 0},{-1,0,1,-1,-1},{0,1,1,-1,-1},{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){
      j=xi + (yi<<9) + (i<<18);
      L[k].push_back(j);
      d[i][xi][yi]=0;
      }
    int dir,x,y,_x,_y,_dir,now,_now;
    int sol=Inf;
    for (;L[0].size()+L[1].size()+L[2].size()>0;++k){
          now=k%3;
          for (;L[now].size()>0;L[now].pop_front()){
                i=L[now].front();
                dir=i>>18;
                x=i&511;
                y=(i>>9)&511;
                //sens trigonometric
                for (i=0;i<3;++i){
                  _x=x+dx[dir][i];
                  _y=y+dy[dir][i];
                  _dir=(dir+i)%8;
                  if (_x>0 && _x<=N && _y>0 && _y<=M && !a[_x][_y])
                   if (d[_dir][_x][_y]>d[dir][x][y]+i){
                    d[_dir][_x][_y]=d[dir][x][y]+i;
                    _now=(now+i)%3;
                    L[_now].push_back(_x+ (_y<<9) + (_dir<<18));
                    if (_x==xf && _y==yf && sol>k+i)
                      sol=k+i; }
                    }  
                //sens antitrigonometric
                for (i=1;i<=2;++i){
                  _x=x+dx[dir][i+2];
                  _y=y+dy[dir][i+1];
                  _dir=(dir-i+8)%8;
                  if (_x>0 && _x<=N && _y>0 && _y<=M && !a[_x][_y])
                   if (d[_dir][_x][_y]>d[dir][x][y]+i){
                    d[_dir][_x][_y]=d[dir][x][y]+i;
                    _now=(now+i)%3;
                    L[_now].push_back(_x+ (_y<<9) + (_dir<<18));
                    if (_x==xf && _y==yf && sol>k+i)
                      sol=k+i; }
                    }  

                }
          }
    if (sol==Inf) sol=-1;
    g<<sol;     
    return 0;
}