Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney
Problem:
https://www.geeksforgeeks.org/problems/rat-in-a-maze-problem/1
Rat in a Maze
Difficulty: Medium Accuracy: 35.75%
Consider a rat placed at position (0, 0) in an n x n square matrix maze[][]. The rat's goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions: 'U'(up), 'D'(down), 'L' (left), 'R' (right).
The matrix contains only two possible values:
• 0: A blocked cell through which the rat cannot travel.
• 1: A free cell that the rat can pass through.
Your task is to find all possible paths the rat can take to reach the destination, starting from (0, 0) and ending at (n-1, n-1), under the condition that the rat cannot revisit any cell along the same path. Furthermore, the rat can only move to adjacent cells that are within the bounds of the matrix and not blocked.
If no path exists, return an empty list.
Note: Return the final result vector in lexicographically smallest order.
Examples:
Input: maze[][] = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]
Output: ["DDRDRR", "DRDDRR"]
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.
Input: maze[][] = [[1, 0], [1, 0]]
Output: []
Explanation: No path exists as the destination cell (1, 1) is blocked.
Input: maze[][] = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: ["DDRR", "RRDD"]
Explanation: The rat has two possible paths to reach the destination: DDRR and RRDD.
Constraints:
2 ≤ n ≤ 5
0 ≤ maze[i][j] ≤ 1
Solution:
class Solution:
def ratInMaze(self, maze):
n = len(maze)
res = []
if maze[0][0] == 0 or maze[n-1][n-1] == 0:
return res
vis = [[0]*n for _ in range(n)]
def dfs(i, j, path):
if i == n-1 and j == n-1:
res.append(path)
return
vis[i][j] = 1
if i+1
dfs(i+1, j, path+'D')
if j-1>=0 and not vis[i][j-1] and maze[i][j-1]:
dfs(i, j-1, path+'L')
if j+1
dfs(i, j+1, path+'R')
if i-1>=0 and not vis[i-1][j] and maze[i-1][j]:
dfs(i-1, j, path+'U')
vis[i][j] = 0
dfs(0, 0, '')
return sorted(res)
Top comments (0)