Cod sursa(job #378175)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 27 decembrie 2009 20:21:18
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>

using namespace std;

#define maxbuf 65536
#define NM 505
#define SM 4000005
#define FOR(i,a,b)for(int i=(a);i<=(b);++i)

FILE*fin=fopen("car.in","r");

char buf[maxbuf],A[NM][NM],pl[10],pc[10],in[SM],tel[10];

int ind,lin,col,wh,N,M,sl,sc,fl,fc,best[SM];

char cost[8][8]={
{4,3,2,1,0,1,2,3},
{3,4,3,2,1,0,1,2},
{2,3,4,3,2,1,0,1},
{1,2,3,4,3,2,1,0},
{0,1,2,3,4,3,2,1},
{1,0,1,2,3,4,3,2},
{2,1,0,1,2,3,4,3},
{3,2,1,0,1,2,3,4}};

queue<int> Q;

inline void refbuf()
{
     int ans=fread(buf,1,maxbuf,fin);  
     if(ans<maxbuf) buf[ans]=0;
     ind=0;
}

inline int readnr()
{
     int ans=0;
     
     one:
         while(ind<maxbuf && !isdigit(buf[ind])) ++ind;
         if(ans==maxbuf)
         {
           refbuf();
           goto one;
         }
     two:
         while(ind<maxbuf && isdigit(buf[ind])) 
         {
           ans=ans*10+buf[ind]-'0';
           ++ind;
         }   
         if(ans==maxbuf)
         {
           refbuf();
           goto two;
         }
    return ans;     
}

inline int codif(int l,int c,int w)
{
    int ans=l;
    ans=(ans<<9)+c;
    ans=(ans<<3)+w;
    
    return ans;   
}

inline void decodif(int state)
{
    lin=(state>>12);
    col=(state>>3)-(lin<<9);
    wh=state-(lin<<12)-(col<<3);
}

int main()
{
    int fans=1000000000;
    
    //freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    
    refbuf();
    
    N=readnr();
    M=readnr();
    
    sl=readnr();
    sc=readnr();
    fl=readnr();
    fc=readnr();
    
    FOR(i,1,N)
      FOR(j,1,M)
        A[i][j]=readnr();  
    
    pl[0]=-1;pl[1]=-1;pl[2]=0;pl[3]=1;pl[4]=1;pl[5]=1;pl[6]=0;pl[7]=-1;
    pc[0]=0;pc[1]=1;pc[2]=1;pc[3]=1;pc[4]=0;pc[5]=-1;pc[6]=-1;pc[7]=-1;
    
    int l,c,w,T;
    /*
    T=readnr();
    
    while(T--)
    {
      l=readnr();
      c=readnr();
      w=readnr();
      
      int nr=codif(l,c,w);
      
      printf("%d\n",nr);
      
      decodif(nr);
      
      printf("%d %d %d\n",lin,col,wh);
    }
    */
    tel[0]=4;
    tel[1]=5;
    tel[2]=6;
    tel[3]=7;
    tel[4]=0;
    tel[5]=1;
    tel[6]=2;
    tel[7]=3;
    
    FOR(i,0,7)
    {
      int nr=codif(sl,sc,i);
      best[nr]=1;
      Q.push(nr);
      in[nr]=1;
    }  
    
    while(!Q.empty())
    {
      int nr=Q.front();
      Q.pop();
      in[nr]=0;
      
      decodif(nr);
      
      l=lin,c=col,w=wh;
      
      FOR(i,0,7)
      {
        int nl=l+pl[i];
        int nc=c+pc[i];
        int nw=tel[i];
        
        if(A[nl][nc]==1) continue;
        if(!nl || !nc) continue;
        if(nl>N || nc>M) continue;
        
        int cost_cur=best[nr]-1+cost[i][w];
        
        int nnr=codif(nl,nc,nw);
        
        if(!best[nnr]||best[nnr]-1>cost_cur)
        {
          best[nnr]=cost_cur+1;
          if(!in[nnr])
          {
            Q.push(nnr);
            in[nnr]=1;
          }
        }
        
        if(nl==fl && nc==fc) fans=min(fans,best[nnr]-1);
      }
    }
    
    if(fans==1000000000) printf("-1\n");
    else printf("%d\n",fans);
    
    return 0;
}