Advertisement
Guest User

Untitled

a guest
Feb 20th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.35 KB | None | 0 0
  1. bool Maze::initSolution() { // Initializing solution; at the end of the program, stack will have all coordinates of the possible path to the end.
  2.     int i = 1, j = 0; // Starting position (1,0)
  3.     bool flag = flag = solveMaze(i, j);// Flag(T/F) to know if any possible path exist or not
  4.  
  5.     cout << "\n\nSolution:\n";// Printing solution
  6.     if (!flag) { cout << "Unsolveable.\n";} // If flag doesn't reach the end-path, could put this before and have a if/else block or in solveMaze
  7.  
  8.     for (int i = 0; i < row; i++) { // Solution path
  9.         cout << grid[i].data() << endl;
  10.     }
  11.     return flag;
  12. }
  13.  
  14. bool Maze::solveMaze(int i, int j) { // Traversing all possible paths
  15.     grid[i][j] = '#'; // Marking visited location
  16.     if (i == (row - 2) && j == (col - 1))
  17.         return true;
  18.     s.push(i, j); // Pushing cordinates in stack
  19.  
  20.  
  21.     bool flag1 = false, flag2 = false, flag3 = false, flag4 = false, check = false; // This was an awful idea.
  22.    
  23.     if (i > 0) { // For moving up
  24.         if (grid[i - 1][j] == ' ') { // Check blank space
  25.             flag1 = solveMaze(i - 1, j);
  26.             if (!flag1) { // If it is wrong path, clear mark i.e. => ' ' and pop from stack all wrong co-ordinates
  27.                 grid[i - 1][j] = ' ';
  28.                 s.pop();
  29.             }
  30.             check = true;
  31.         }
  32.     }
  33.  
  34.     if (j > 0) { // For moving left
  35.         if (grid[i][j - 1] == ' ') { // Check blank space
  36.             flag2 = solveMaze(i, j - 1);
  37.             if (!flag2) { // If it is wrong path, clear mark i.e. => ' ' and pop from stack all wrong co-ordinates  
  38.                 grid[i][j - 1] = ' ';
  39.                 s.pop();
  40.             }
  41.             check = true;
  42.         }
  43.     }
  44.     if (i < (row - 1)) { //For moving down
  45.         if (grid[i + 1][j] == ' ') { // Check blank space
  46.             flag3 = solveMaze(i + 1, j);
  47.             if (!flag3) {// If it is wrong path, clear mark i.e. => ' ' and pop from stack all wrong co-ordinates  
  48.                 grid[i + 1][j] = ' ';
  49.                 s.pop();
  50.             }
  51.             check = true;
  52.         }
  53.     }
  54.     if (j < (col - 1)) { // For moving right
  55.         if (grid[i][j + 1] == ' ') { // Check blank space
  56.             flag4 = solveMaze(i, j + 1);
  57.             if (!flag4) { // If it is wrong path, clear mark i.e. => ' ' and pop from stack all wrong co-ordinates  
  58.                 grid[i][j + 1] = ' ';
  59.                 s.pop();
  60.             }
  61.             check = true;
  62.         }
  63.     }
  64.     if (!check) { // If cannot moving in to any new location i.e. dead end, return false
  65.         return false;
  66.     }
  67.  
  68.     return flag1 || flag2 || flag3 || flag4; // If any of the paths can reach to the destination it will return true, else return false
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement