Cod sursa(job #202919)

Utilizator floringh06Florin Ghesu floringh06 Data 12 august 2008 11:02:25
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <cstdio>  
#include <cstring>

using namespace std;

#define FIN "car.in"
#define FOUT "car.out"
#define MAX_N 505  
#define MAX_C 22
 
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1 ,-1 ,-1};   
 
int D[MAX_N][MAX_N];
int dist[1 << MAX_C];
int N, M;
int xs, ys, xf, yf;

int BEST;  

struct NOD  
{  
     int nod;  
     NOD *next;  
} *A[MAX_N * MAX_N << 1];  

    inline int MIN (int a, int b)
    {
            if (a < b) return a; else return b;
    }       

    void renew(int nod, int d)  
    {  
           if(d < dist[nod])  
           {  
              NOD *q=new NOD;  
              dist[nod] = d;  
              q->nod = nod;  
              q->next = A[d];  
              A[d] = q;  
           }  
    }  
   
    void solve()  
    {  
         int i, j, x, y, d, nx, ny, nd;  
         NOD *q;  
   
         for(i = 1; i <= N; ++i)  
             for(j = 1; j <= M; ++j)  
                 for(d = 0; d < 8; ++d)  
                       dist[(i << 12) + (j << 3) + d] = N * M << 1;  
    
         for(d = 0;d < 8; ++d)  
         {  
            q = new NOD;  
            x = (xs << 12) + (ys << 3) + d;  
            dist[x] = 0;  
            q->nod = x;  
            q->next = A[0];  
            A[0] = q;  
         }  
  
         for(i = 0; i < N * M << 1; ++i)  
           while(A[i])  
           {  
              j = A[i]->nod, A[i] = A[i]->next;  
              if(dist[j] < i)continue;  
              //decodific
              d = j & 7, y = j >> 3 & 511, x = j >> 12;  
   
              nx = x + dx[d], ny = y + dy[d];  
              
              if(nx && nx <= N && ny && ny <= M && !D[nx][ny]) renew((nx << 12) + (ny << 3) + d, dist[j]);  
              
              int it;
              for (it = 1; it <= 2; ++it)
              {
                  nd = d + it;  
                  if(nd > 7) nd -= 8;  
                  nx=x+dx[nd], ny=y+dy[nd];  
                  if(nx && nx <= N && ny && ny <= M && !D[nx][ny]) renew((nx << 12) + (ny << 3) + nd, dist[j] + it);  
              }

              for (it = -1; it >= -2; --it)   
              {
                  nd = d + it;  
                  if(nd < 0) nd += 8;  
                  nx = x + dx[nd], ny = y + dy[nd];  
                  if(nx && nx <= N && ny && ny <= M && !D[nx][ny]) renew((nx << 12) + (ny << 3) + nd, dist[j] - it);  
              }
           }  
   
           BEST = N * M << 1;  
           for(d = 0; d < 8; ++d)  
                 BEST = MIN(BEST, dist[(xf << 12) + (yf << 3) + d]);  
           if(BEST == N * M << 1) BEST = -1;  
    }  
      
    int main()  
    {  
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        int i, j;
        scanf ("%d %d %d %d %d %d", &N, &M, &xs, &ys, &xf, &yf);
        for (i = 1; i <= N; ++i)
            for (j = 1; j <= M; ++j)
                scanf ("%d", D[i] + j);
            
        solve();  
     
        printf ("%d\n", (int) BEST);
        return 0;  
    }