TCS OA-30 2024
Problem Description
Given an N x N matrix where 1 represents a cell that can be visited and 0 represents a blocked cell, find all possible paths from the top-left cell (0, 0) to the bottom-right cell (N-1, N-1). The rat can only move in four directions: up, down, left, and right.
Input Format
- The first line contains an integer N, representing the size of the square matrix.
- A 2D matrix of size N x N representing the maze.
Output Format
All possible paths from the top-left cell to the bottom-right cell, represented as a sequence of moves ('U', 'D', 'L', 'R').
Constraints
- 1 ≤ N ≤ 10
Example
Sample Input:
4
[[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 0, 0],
[0, 1, 1, 1]]
Sample Output:
DDRDRR DRDDRR
Explanation:
The rat can reach the destination by following two possible paths:
- DDRDRR: Down, Down, Right, Down, Right, Right
- DRDDRR: Down, Right, Down, Down, Right, Right