Advertisement
iamyeasin

Untitled

Apr 8th, 2018
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define     sf      scanf
  3. #define     pf      printf
  4. #define     inf     INT_MAX
  5. #define     dbg     cout << "Debug" << endl;
  6. #define     MAX     1024
  7. #define     block   -1
  8. #define     white   +0
  9. #define     noway   -3
  10. #define     source  -4
  11. #define     goal    -5
  12.  
  13. using namespace std;
  14.  
  15. void clr();
  16. void printGrid();
  17. void printGrid2();
  18. void printGrid3();
  19.  
  20. vector < int > adjList[1024];
  21. char ans[28][28];
  22.  
  23. int dx[] = { +0, -1, +0, +1 };
  24. int dy[] = { -1, +0, +1, +0 };
  25.  
  26.  
  27. int nodes,start,edges,n,a,b,c=0,l,w,sx,sy,gx,gy,flag = false,off = false;
  28. int visited[1025] ,d[1024],par[1024];
  29. int cost[1024][1024];
  30. int grid[ MAX ][ MAX ];
  31.  
  32. bool isOk( int x, int y ){
  33.     return ( x >= 1 && (x <= (l << 2)+1) && y >= 1 && (y<=(w<<1)+1) );
  34. }
  35.  
  36. bool isValid( int cd, int pd ){
  37.     if( (cd == 2 && pd == 0) || ( pd == 2 && cd == 0 ) || ( cd == 3 && pd == 1) ||
  38.         (cd == 1 && pd == 3) ) return false;
  39.     else return true;
  40. }
  41.  
  42. bool isNoMove( int x, int y , int pd ){
  43.     for( int i=0; i<4; i++ ){
  44.         int mx = dx[i] + x;
  45.         int my = dy[i] + y;
  46.         if( grid[mx][my] == white && isOk(mx,my)  && isValid(i,pd) ) return false;
  47.     }
  48.     return true;
  49. }
  50.  
  51. void solve( int x, int y, int pd , int c ){ // was a fuck
  52.     if( isNoMove( x, y, pd ) ){
  53.         grid[x][y] = noway;
  54.         return;
  55.     }
  56.  
  57.     for( int i=0; i<4; i++ ){
  58.         int px = dx[i] + x;
  59.         int py = dy[i] + y;
  60.         int fx = ( dx[i]<<1 ) + x,fy = ( dy[i]<<1 ) + y;
  61.        
  62.         if( grid[fx][fy] == goal ){
  63.             grid[fx][fy] = (c);
  64.             flag = 1; return;
  65.         }
  66.        
  67.         if( isOk(fx,fy) && grid[px][py] == white && isValid(i, pd) && !flag ){
  68.             grid[fx][fy] = (c );
  69.             solve( fx, fy, i , c + 1 );
  70.             if(!flag) grid[fx][fy] =noway;
  71.         }
  72.     }
  73. }
  74.  
  75.  
  76. int main(){
  77.     #ifndef ONLINE_JUDGE
  78.         freopen("in.txt","rt",stdin);
  79.         freopen("outsss.txt","wt",stdout);
  80.     #endif
  81.  
  82.     int tc= 0;
  83.     while ( sf("%d %d %d %d %d %d", &l, &w, &sx, &sy, &gx, &gy) , l+w+sx+sy+gx+gy ){
  84.         for( int i=1; i<=l; i++ ){
  85.             for( int j=1; j<=w; j++ ){
  86.                 sf("%d",&a);
  87.                 if( a == 1 ) grid[(i << 1)][( j<<1 ) + 1] = block;
  88.                 else if( a == 2 ) grid[(i << 1)+1][( j<<1 )] = block;
  89.                 else if( a == 3 ) { grid[(i << 1)][( j<<1 ) + 1] = block; grid[(i << 1)+1][( j<<1 )] = block; }
  90.             }
  91.         }
  92.  
  93.         grid[sx<<1][sy<<1] = source; grid[gx<<1][gy<<1] = goal;
  94.         for( int i=1; i<=((w<<1)+1); i++ ) { grid[1][i] = block; grid[(l<<1)+1][i] = block; }
  95.         for( int i=1; i<=((l<<1)+1); i++ ) { grid[i][1] = block; grid[i][(w<<1)+1] = block; }
  96.  
  97.         int cur = 1,tx,ty;
  98.         sx = sx<<1;
  99.         sy = sy<<1;
  100.  
  101.         if( grid[sx][sy] != goal )grid[sx][sy] = (++c);
  102.         solve(sx,sy,-1,2);
  103.        // printGrid();
  104.         printf("Maze %d\n\n", ++tc);
  105.         memset( ans, '\0', sizeof ans );
  106.         printGrid2();
  107.         puts("");
  108.         puts("");
  109.         clr();
  110.     }
  111.  
  112.     return 0;
  113. }
  114.  
  115. void clr(){
  116.     flag= false, c=0;
  117.     memset( grid, 0, sizeof grid );
  118.     memset( ans, '\0', sizeof ans );
  119. }
  120.  
  121. void printGrid(){
  122.     for( int i=1; i<= ( (l<<1)+1) ; i++ ){
  123.         for( int j=1; j<= ( w<<1)+1; j++ ){
  124.             printf("%2d ", grid[i][j] );
  125.         }
  126.         puts("");
  127.     }
  128. }
  129.  
  130. void printGrid2(){
  131.     for( int i=1; i<=(w<<2)+1 ; i++ ){
  132.         if( i%4 == 1 ) { ans[1][i] = '+'; ans[(l<<1)+1][i] = '+';}
  133.         else { ans[1][i] = '-';  ans[(l<<1)+1][i] = '-';}
  134.     }
  135.     for( int i=1; i<=(l<<1)+1; i+=2 ){
  136.         for(int j=1; j<=(w<<2)+1; j+=4){
  137.             ans[i][j] = '+';
  138.         }
  139.     }
  140.  
  141.     for( int i=1; i<=(l<<1)+1; i++ ){
  142.         if(i&1){
  143.             ans[i][1] = '+'; ans[i][(w<<2)+1] = '+';
  144.         }
  145.         else{
  146.              ans[i][1] = '|'; ans[i][(w<<2)+1] = '|';
  147.         }
  148.     }
  149.  
  150.  
  151.     for( int i=2; i<=(l<<1); i+=2 ){
  152.         for( int j=2; j<=(w<<2); j+=2 ){
  153.             int v = grid[i][j];
  154.             if( v == noway ){
  155.                 ans[i][j*2] = '?'; ans[i][(j*2)-1] = '?';
  156.                 ans[i][(j*2)-2] = '?';
  157.             }
  158.             else if( v > 0 )  {
  159.                 if( v <= 9 ){
  160.                     ans[i][j<<1] = v + '0';
  161.                     ans[i][(j<<1)-1] = ' ';
  162.                     ans[i][(j<<1)-1] = ' ';
  163.                 }
  164.                 else{
  165.                     if( v<=99 ){
  166.                         char d1 = v%10+'0'; char d2 = (v/10)+'0';
  167.                         ans[i][j<<1] = d1;
  168.                         ans[i][(j<<1)-1] = d2;
  169.                         ans[i][(j<<1)-1] = ' ';
  170.                     }
  171.                     else{
  172.                         ans[i][j<<1] = v%10+'0';
  173.                         ans[i][(j<<1)-1] = ((v/10)%10)+'0';
  174.                         ans[i][(j<<1)-1] = ((v/10)/10)+'0';
  175.                     }
  176.                 }
  177.             }
  178.             if(grid[i][j+1] == block ) ans[i][(j<<1)+1] = '|';
  179.                 if(grid[i+1][j] == block){
  180.                     ans[i+1][j*2] = '-'; ans[i+1][(j*2)-1] = '-';
  181.                     ans[i+1][(j*2)-2] = '-';
  182.             }
  183.         }
  184.     }
  185.  
  186.     for( int i=1; i<=(l<<1)+1; i++ ){
  187.         for( int j=1; j<=(w<<2)+1; j++ ){
  188.             if( (ans[i][j]>='0' && ans[i][j]<='9')|| ans[i][j] == '+' || ans[i][j] == '?' ||  ans[i][j] == '-' || ans[i][j] == '|' ){
  189.                 pf("%c",ans[i][j]);
  190.             }
  191.             else pf(" ");
  192.         }
  193.         puts("");
  194.     }
  195.  
  196. }
  197.  
  198.  
  199. /*
  200.  
  201. +---+---+---+
  202. |  1|???|  5|
  203. +   +   +   +
  204. |  2   3   4|
  205. +---+---+---+
  206.  
  207. +---+---+---+
  208. |??? ???|???|
  209. +   +---+   +
  210. |  3   4   5|
  211. +   +---+   +
  212. |  2   1|  6|
  213. +   +---+   +
  214. |       |  7|
  215. +---+---+---+
  216.  
  217.  
  218. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement