Rat in a Maze
Advanced Backtracking DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Rat in a Maze: Find all possible paths for a rat to travel from the top-left to bottom-right of an N x N matrix, moving only through cells with value 1 and not visiting a cell more than once., Recursion, Backtracking, Matrices, Two-dimensional Array Traversal, Depth-First Search, Arrays, String Manipulation, Sorting, Time Complexity, Space Complexity, Big O Notation, string operations, visited tracking, backtracking, matrix traversal, recursion, time complexity analysis, Backtracking Constraints.
Rat in a Maze Consider a rat placed at (0, 0) in a square matrix of order N N. It has to reach the destination at (N 1, N 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are 'U' (up), 'D' (down), 'L' (left), 'R' (right). A value of 0 at a cell in the matrix represents that it is blocked and the rat cannot move to it, while a value of 1 at a cell represents that the rat can travel through it. Note : In a path, no cell can be visited more than one time. The paths should be printed in lexicographical (sorted) order. Input Specification The first line contains an integer N, the order of the square matrix. The next N lines contain N integers each, representing the m[][] matrix. Output Specification Print all valid paths in lexicographical order, separated by spaces. If no path exists, print 1. Constraints 1 <= N <= 5 0 <= m[i][j] <= 1 Sample Test Cases Example 1: Explanation: The rat can reach the destination at (3, 3) from (0, 0) by two paths: DRDDRR and DDRDRR. When printed in sorted order, we get DDRDRR DRDDRR. Example 2: Explanation: No path exists from (0, 0) to (1, 1) as the destination cell is blocked in this specific matrix. Also, even if the destination wasn't blocked, the path through (1,0) to (1,1) would require movement through 0 if m[1][1] was 1.