Guest User

Untitled

a guest
Jan 25th, 2020
362
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. int n;
  4. int check[10][10];
  5. void traverse( int ** m, int row, int col ){
  6.     //base cases
  7.     if(row >= n || col >= n || row < 0 || col < 0)
  8.         return;
  9.     if(check[row][col] == -1|| m[row][col] == 0)
  10.         return;
  11.        
  12.     //marking visited boxes with -1;
  13.     check[row][col] = -1;
  14.    
  15.     //recursive cases
  16.     traverse( m,  row - 2,  col - 1 );
  17.     traverse( m,  row - 2,  col + 1 );
  18.    
  19.     traverse( m,  row - 1,  col - 2 );
  20.     traverse( m,  row - 1,  col + 2 );
  21.    
  22.     traverse( m,  row + 1,  col - 2 );
  23.     traverse( m,  row + 1,  col + 2 );
  24.    
  25.     traverse( m,  row + 2,  col - 1 );
  26.     traverse( m,  row + 2,  col + 1 );
  27.    
  28.    
  29. }
  30.  
  31. /*
  32. (r-2,c-1), (r-2,c+1), (r-1,c-2), (r-1,c+2), (r+1,c-2), (r+1,c+2), (r+2,c-1), or (r+2,c+1).
  33. */
  34. int main(){
  35.    
  36.     cin>>n;
  37.     int **m = new int*[n];
  38.     for(int i = 0; i < n; i++){
  39.         m[i] = new int[n];
  40.     }
  41.    
  42.     for(int i = 0; i < n; i++)
  43.         for(int j = 0; j < n; j++)
  44.             cin>>m[i][j];
  45.     traverse(m, 0, 0);
  46.     int count = 0;
  47.     //checking out how many rows remain unvisited
  48.     check[0][0] = -1;
  49.     for(int i = 0; i < n; i++)
  50.     {
  51.         for(int j = 0; j < n; j++){
  52.            // cout<<m[i][j]<<" ";
  53.             if(check[i][j]  != -1)
  54.                 count++;
  55.         }
  56.       //  cout<<endl;
  57.     }
  58.     cout<<count<<endl;
  59.    
  60.    
  61.     return 0;
  62. }
Add Comment
Please, Sign In to add comment