19. Backtracking/rat_in_a_maze.cpp
bool solveMazeUtil(
	int maze[N][N], int x,
	int y, int sol[N][N])
{
	// if (x, y is goal) return true
	if (
		x == N - 1 && y == N - 1
		&& maze[x][y] == 1) {
		sol[x][y] = 1;
		return true;
	}

	// Check if maze[x][y] is valid
	if (isSafe(maze, x, y) == true) {
		// Check if the current block is already part of solution path.
		if (sol[x][y] == 1)
			return false;
	
		// mark x, y as part of solution path
		sol[x][y] = 1;

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

		/* If moving in x direction doesn't give solution then Move down in y direction */
		if (solveMazeUtil(
				maze, x, y + 1, sol)
			== true)
			return true;
	
		/* If none of the above movements
		work then BACKTRACK: unmark
		x, y as part of solution path */
		sol[x][y] = 0;
		return false;
	}

	return false;
}
/* A recursive utility function to solve Maze problem */
A recursive utility function to solve Maze problem
A recursive utility function to solve Maze problem
bool solveMazeUtil(
	int maze[N][N], int x,
	int y, int sol[N][N])
{
	if (
		x == N - 1 && y == N - 1
		&& maze[x][y] == 1) {
		sol[x][y] = 1;
		return true;
	}
	if (isSafe(maze, x, y) == true) {
		if (sol[x][y] == 1)
			return false;
		sol[x][y] = 1;
		if (solveMazeUtil(
				maze, x + 1, y, sol)
			== true)
			return true;
		if (solveMazeUtil(
				maze, x, y + 1, sol)
			== true)
			return true;
		sol[x][y] = 0;
		return false;
	}
	return false;
}
bool solveMazeUtil ( int maze [ N ] [ N ] , int x , int y , int sol [ N ] [ N ] ) { if ( x == N - 1 && y == N - 1 && maze [ x ] [ y ] == 1 ) { sol [ x ] [ y ] = 1 ; return true ; } if ( isSafe ( maze , x , y ) == true ) { if ( sol [ x ] [ y ] == 1 ) return false ; sol [ x ] [ y ] = 1 ; if ( solveMazeUtil ( maze , x + 1 , y , sol ) == true ) return true ; if ( solveMazeUtil ( maze , x , y + 1 , sol ) == true ) return true ; sol [ x ] [ y ] = 0 ; return false ; } return false ; }
A recursive utility function to solve Maze problem
A recursive utility function to solve Maze problem
// if (x, y is goal) return true // Check if maze[x][y] is valid // Check if the current block is already part of solution path. // mark x, y as part of solution path /* Move forward in x direction */ /* If moving in x direction doesn't give solution then Move down in y direction */ /* If none of the above movements
		work then BACKTRACK: unmark
		x, y as part of solution path */