Cod sursa(job #2130)

Utilizator stef2nStefan Istrate stef2n Data 16 decembrie 2006 05:32:16
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <stdio.h>
#include <string.h>

#define infile "car.in"
#define outfile "car.out"
#define codif(lin,col,dir) (((dir<<9) | lin)<<9) | col
#define decodif_lin(nr) LIN
#define decodif_col(nr) COL
#define valid_poz(lin,col) ((lin>=0) && (col>=0) && (lin<m) && (col<n) && !drum[lin][col])
#define DMAX 505
const int NMAX=(codif(500,500,7)+5);
struct NOD{int x; NOD *adr;};
const int dlin[]={-1,-1,-1,0,1,1,1,0};
const int dcol[]={-1,0,1,1,1,0,-1,-1};
int _newlin,_newcol,_newnr;

FILE *fin,*fout;
NOD *lista[2],*endlista[2];
char drum[DMAX][DMAX];
short int startlin,startcol,endlin,endcol;
int m,n;
char vizitat[NMAX];
short int LIN,COL,DIR;

inline char my_abs(char x)
  {
   if(x<0)
     return -x;
   return x;
  }

inline int decodif_dir(int nr)
  {
   COL = nr & 511;
   nr>>=9;
   LIN = nr & 511;
   DIR = nr>>9;
   return DIR;
  }

inline void adaug_dr(NOD *(&prim), NOD *(&last), int x)
  {
   NOD *a=new NOD;
   a->x=x;
   a->adr=NULL;
   if(!prim)
     prim=last=a;
   else
     {last->adr=a;
      last=a;}
  }

void citire()
  {
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d",&m,&n);
   fscanf(fin,"%d %d %d %d",&startlin,&startcol,&endlin,&endcol);
   startlin--; startcol--; endlin--; endcol--;
   for(int i=0;i<m;i++)
      for(int j=0;j<n;j++)
         fscanf(fin,"%d",&drum[i][j]);
   fclose(fin);
  }

void exploreaza()
  {
   for(int k=0;k<NMAX-2;k++)
      {
       while(lista[0])
            {
             if(vizitat[lista[0]->x]==k)
              {
               decodif_dir(lista[0]->x);

               _newlin=LIN+dlin[(DIR+4)%8];
               _newcol=COL+dcol[(DIR+4)%8];
               if(valid_poz(_newlin,_newcol))
                 {
                  _newnr=codif(_newlin,_newcol,DIR);
                  if(vizitat[_newnr]==-1 || k<vizitat[_newnr])
                    {vizitat[_newnr]=k;
                     adaug_dr(lista[0],endlista[0],_newnr);}
                 }

               _newnr=codif(LIN,COL,(DIR+1)%8);
               if(vizitat[_newnr]==-1 || k+1<vizitat[_newnr])
                 {vizitat[_newnr]=k+1;
                  adaug_dr(lista[1],endlista[1],_newnr);}

               _newnr=codif(LIN,COL,(DIR+7)%8);
               if(vizitat[_newnr]==-1 || k+1<vizitat[_newnr])
                 {vizitat[_newnr]=k+1;
                  adaug_dr(lista[1],endlista[1],_newnr);}

               if(LIN==endlin && COL==endcol)
                 return;
              }
             lista[0]=lista[0]->adr;
             if(!lista[0])
               endlista[0]=NULL;
            }
       lista[0]=lista[1];
       endlista[0]=endlista[1];
       lista[1]=endlista[1]=NULL;
       if(!lista[0])
         return;
      }
  }


int main()
{
int i;
citire();
lista[0]=lista[1]=NULL;
endlista[0]=endlista[1]=NULL;
memset(vizitat,-1,NMAX-2);
for(i=0;i<8;i++)
   {vizitat[codif(startlin,startcol,i)]=0;
    adaug_dr(lista[0],endlista[0],codif(startlin,startcol,i));}
exploreaza();
int min=1000000000;
for(i=0;i<8;i++)
   if(min>vizitat[codif(endlin,endcol,i)] && vizitat[codif(endlin,endcol,i)]!=-1)
     min=vizitat[codif(endlin,endcol,i)];
if(min==1000000000)
  min=-1;
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",min);
fclose(fout);
return 0;
}