Advertisement
iamyeasin

localBackTrack

Apr 10th, 2018
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 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. long grid[ MAX ][ MAX ];
  16. int visited[ MAX ][ MAX ];
  17.  
  18. int dx[] = { +0, -1, +0, +1 };
  19. int dy[] = { -1, +0, +1, +0 };
  20.  
  21. int sx,sy,gx,gy,l,w,flag = false;
  22.  
  23. void clr(){
  24.     for( int i=1; i<=l; i++ ){
  25.         for( int j=1; j<=w; j++ ){
  26.             grid[i][j] = visited[i][j] = 0;
  27.         }
  28.     }
  29.     flag = false;
  30. }
  31.  
  32. bool isOk( int x, int y ){
  33.     return ( x >= 1 && ( x <= l) && y >= 1 && (y<=w) );
  34. }
  35.  
  36. bool isValid( int mdx, int mdy ){
  37.     if( isOk(mdx,mdy) )
  38. }
  39.  
  40. bool isNoMove( int x, int y , int pd ){
  41.     for( int i=0; i<4; i++ ){
  42.         int mx = dx[i] + x;
  43.         int my = dy[i] + y;
  44.         if( grid[mx][my] == white && isOk(mx,my)  && isValid(i,pd) ) return false;
  45.     }
  46.     return true;
  47. }
  48.  
  49.  
  50. void solve( int x, int y, int pd , int c ){ // was a fuck
  51.     if (grid[x][y] == goal ){
  52.         grid[x][y]=c;
  53.         flag = 1;
  54.         return;
  55.     }
  56.  
  57.     if ( isNoMove(x,y,pd) ){
  58.         grid[x][y]=noway;
  59.         return;
  60.     }
  61.  
  62.     for ( int i = 0; i < 4; i++ ){
  63.         int mdx = dx[i] + x;
  64.         int mdy = dy[i] + y;
  65.        
  66.         if( isOk(mdx,mdy) && !flag && grid[mdx][mdy] <= 0 &&  isValid(mdx,mdy) ){
  67.             solve(mdx,mdy,c+1);
  68.             if( flag )grid[x][y] = c;
  69.             else if( !flag ) grid[x][y] = noway;
  70.         }
  71.     }
  72.            
  73. }
  74.  
  75.  
  76. int main(){
  77.     #ifndef ONLINE_JUDGE
  78.         freopen("in.txt","rt",stdin);
  79.         freopen("out.txt","wt",stdout);
  80.     #endif
  81.  
  82.     while( sf("%d %d %d %d %d %d", &l,&w,&sx,&sy,&gx,&gy) , l+w+sx+sy+gx+gy ){
  83.         clr();
  84.         grid[sx][sy] = source; grid[gx][gy] = goal;
  85.         for( int i=1; i<=l; i++ ){
  86.             for( int j=1; j<=w; j++ ){
  87.                 sf( "%d",&visited[i][j] );
  88.             }
  89.         }
  90.  
  91.         solve();
  92.     }
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement