Rat In a Maze Problem Statement

Given a N * N maze with a rat placed at position MAZE[0][0], find and print all possible paths for the rat to reach its destination at MAZE[N-1][N-1]. The rat is allowed to move in any direction: left, right, up, and down.

The value of each cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked (the rat cannot enter), whereas cells with value 1 are open (the rat can move through them).

Input:

The first line of input contains an integer 'N' indicating the maze's dimension. The next 'N' lines contain 'N' space-separated integers representing the cells of the maze.

Output:

For each test case, return the path from the start position to the destination. The path should be represented with 1s for cells that are part of the solution, and 0s for others. Output each path for different test cases on separate lines.

Example:

Input:

N = 3 MAZE = [[1, 0, 0], [1, 1, 0], [0, 1, 1]]

Output:

[[1, 0, 0], [1, 1, 0], [0, 1, 1]]

Explanation:

The rat can move from the start to the destination following open cells marked by 1s.

Constraints:

1 ≤ N ≤ 10

0 ≤ MAZE[i][j] ≤ 1

The rat can only move through cells marked as 1.

Time Limit: 1 sec

Question

Rat In a Maze Problem Statement

Given a N * N maze with a rat placed at position MAZE[0][0], find and print all possible paths for the rat to reach its destination at MAZE[N-1][N-1]. The rat is allowed to move in any direction: left, right, up, and down.

The value of each cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked (the rat cannot enter), whereas cells with value 1 are open (the rat can move through them).

Input:

The first line of input contains an integer 'N' indicating the maze's dimension.
The next 'N' lines contain 'N' space-separated integers representing the cells of the maze.

Output:

For each test case, return the path from the start position to the destination. The path should be represented with 1s for cells that are part of the solution, and 0s for others. Output each path for different test cases on separate lines.

Example:

Input:

N = 3
MAZE = [[1, 0, 0], [1, 1, 0], [0, 1, 1]]

Output:

[[1, 0, 0], [1, 1, 0], [0, 1, 1]]

Explanation:

The rat can move from the start to the destination following open cells marked by 1s.

Constraints:

1 ≤ N ≤ 10
0 ≤ MAZE[i][j] ≤ 1
The rat can only move through cells marked as 1.
Time Limit: 1 sec

Accepted Answer

The problem involves finding all possible paths for a rat to reach its destination in a maze.

Use backtracking to explore all possible paths in the maze.
Mark visited cells to avoid revisiting them.
Return the path once the destination is reached.
Handle edge cases like blocked cells and out-of-bounds movements.

Accepted Answer

trivial, start with {0,0} nd simply change it to -1 look for all four direction [ifValid] via recursion, change it back to 1;

if you reach {n-1,n-1} just add this to a answer vector.

Return size of this vector