Cod sursa(job #129111)

Utilizator tErMyAndrei Panturu tErMy Data 28 ianuarie 2008 17:40:30
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
 #include <stdio.h>  
 #include <string.h>  
   
 int n, m;  
   
 int a[510][510];  
  
 int dx[] = {-1,-1, 0, 1, 1, 1, 0,-1};  
 int dy[] = { 0, 1, 1, 1, 0,-1,-1,-1};  
   
 int cur[2000010];  
 int urm[2000010];  
   
 char viz[8][510][510];  
   
 int main()  
 {  
     int i, j, pc, qc, pu, qu, x, y, xb, yb, xf, yf, dir;  
   
     freopen("car.in", "r", stdin);  
     freopen("car.out", "w", stdout);  
   
     scanf("%d %d", &n, &m);  
   
     scanf("%d %d %d %d", &xb, &yb, &xf, &yf);  
   
     for (i = 1; i <= n; i++)  
         for (j = 1; j <= m; j++)  
             scanf("%d", &a[i][j]);  
   
     for (i = 0; i <= n+1; i++)  
     {  
         a[i][0] = 1;  
         a[i][m+1] = 1;  
     }  
     for (j = 0; j <= m+1; j++)  
     {  
         a[0][j] = 1;  
         a[n+1][j] = 1;  
     }  
       
   
     for (i = 0; i < 8; i++)  
     {  
         cur[i] = xb + (yb << 9) + (i << 18);  
         viz[i][xb][yb] = 1;  
     }  
   
     pc = 0;  
     qc = 7;  
   
     pu = 0;  
     qu = -1;  
   
     int cost = 0;  
     int e = 0;  
   
     while (1)  
     {  
         //expandez cur pana nu mai pot  
   
         while (pc <= qc)  
         {  
             x = cur[pc] & 511;  
             y = (cur[pc] >> 9) & 511;  
   
             if (x == xf && y == yf)  
             {  
                 e = 1;  
                 break;  
             }  
             dir = cur[pc] >> 18;  
               
             // acu mut una in directie  
   
             if (!viz[dir][x + dx[dir]][y + dy[dir]] && !a[x + dx[dir]][y + dy[dir]])  
             {  
                 cur[++qc] = x + dx[dir] + ((y + dy[dir]) << 9) + (dir << 18);  
                 viz[dir][x + dx[dir]][y + dy[dir]] = 1;  
             }  
   
             pc++;  
         }  
  
         for (i = 0; i <= qc; i++)  
         {  
             x = cur[i] & 511;  
             y = (cur[i] >> 9) & 511;  
             dir = cur[i] >> 18;  
   
             // il mut cu o directie in plus  
             if (!viz[(dir + 1) & 7][x][y])  
             {  
                 urm[++qu] = x + (y << 9) + (((dir + 1) & 7) << 18);  
                 viz[(dir + 1) & 7][x][y] = 1;  
             }  
   
             //il mut cu o directie in minus  
             dir--;  
             if (dir < 0) dir = 7;  
   
             if (!viz[dir][x][y])  
             {  
                 urm[++qu] = x + (y << 9) + (dir << 18);  
                 viz[dir][x][y] = 1;  
             }             
         }  
   
         if (e) break;  
         if (qu == -1)   
         {  
   
             cost = -1;  
             break;  
         }  
   
         cost ++;  
   
         memcpy(cur, urm, sizeof(cur));  
   
         pc = 0;  
         qc = qu;  
         qu = -1;  
     }  
   
     printf("%d\n", cost);  
   
   
 fclose(stdin);  
 fclose(stdout);  
 return 0;  
 }