Use C++ to complete the operation. Specification A maze is a rectangular area wi

Question

Use C++ to complete the operation.

Specification A maze is a rectangular area with an entrance and an exit. The interior of the maze contains walls or obstacles that one cannot walk through. In our mazes these obstacles are placed along rows and columns that are parallel to the rectangular boundary of the maze. The entrance is at the upper-left corner, and the exit is at the lower-right corner as show in the figure 1 m columns wall Entrance (1,1) Can be reached Obstacles n rows Exit wall Figure 1: A maze

Explanation / Answer

#include <iostream>

using namespace std;

#define N 4
#define M 4

bool solveRatMazeUtil(int maze[N][M], int x, int y, int sol[N][M]);

/* A utility function to print solution matrix sol[N][M] */
void printSolution(int solution[N][M])
{
cout<<"Solution path denoted by 1's ";
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
cout << solution[i][j] << " ";
cout << " ";
}
}

/* A utility function to check if x,y is valid index for N*N maze */
bool isSafe(int maze[N][M], int x, int y)
{
// if (x,y outside maze) return false
if(x >= 0 && x < N && y >= 0 && y < M && maze[x][y] == 0)
return true;

return false;
}

/* This function solves the Maze problem using Backtracking.*/
bool solveRatMaze(int maze[N][M])
{
int solution[N][M] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};

if(solveRatMazeUtil(maze, 0, 0, solution) == false)
{
printf("Solution doesn't exist");
return false;
}

printSolution(solution);
return true;
}

/* A recursive utility function to solve Maze problem */
bool solveRatMazeUtil(int maze[N][M], int x, int y, int solution[N][M])
{
// if (x,y is goal) return true
if(x == N-1 && y == M-1)
{
solution[x][y] = 1;
return true;
}

// Check if maze[x][y] is valid
if(isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
solution[x][y] = 1;

/* Move forward in x direction */
if (solveRatMazeUtil(maze, x+1, y, solution) == true)
return true;

/* If moving in x direction doesn't give solution then
Move down in y direction */
if (solveRatMazeUtil(maze, x, y+1, solution) == true)
return true;

/* If none of the above movements work then BACKTRACK:
unmark x,y as part of solution path */
solution[x][y] = 0;
return false;
}

return false;
}

// driver program to test above function
int main()
{
int maze[N][M] = { {0, 1, 1, 1},
{0, 0, 1, 0},
{1, 0, 1, 1},
{0, 0, 0, 0}
};

solveRatMaze(maze);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.