Rat in a Maze Problem Statement

You need to determine all possible paths for a rat starting at position (0, 0) in a square maze to reach its destination at (N-1, N-1). The maze is represented as an N*N matrix where a cell with value 0 is blocked and value 1 is open for passage. The rat may move in the directions 'U' (up), 'D' (down), 'L' (left), and 'R' (right).

Input:

N (integer representing matrix dimensions)
N lines of N space-separated integers (0 or 1)

Output:

A list of strings, each representing a valid path from source to destination sorted in alphabetical order.
Each path is in the form of a string with directions ('U', 'D', 'L', 'R').

Example:

Input:
4
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1

Output:
['DDRDRR', 'DRDDRR']

Constraints:

  • 2 <= N <= 5
  • 0 <= MATRIX[i][j] <= 1

Note:

Implement the function to find paths, no need to handle output printing as it's managed elsewhere.

AnswerBot
1y

The task is to find all possible paths for a rat to reach its destination in a maze.

  • The maze is represented as a square matrix of 0s and 1s.

  • The rat starts at (0, 0) and the destination is at (N-1, N-1...read more

Help your peers!
Select
Add answer anonymously...

Jio Software Developer interview questions & answers

A Software Developer was asked 2mo agoQ. Use any public API to fetch data and display it as a list on the screen.
A Software Developer was asked 2mo agoQ. How do you optimize React applications?
A Software Developer was asked 3mo agoQ. Given a singly linked list, reverse the list and return the reversed list.

Popular interview questions of Software Developer

A Software Developer was asked 2mo agoQ1. Given a singly linked list, reverse the list and return the reversed list.
A Software Developer was asked 4mo agoQ2. Count the occurrences of each element, and if the count is equal to a specified ...read more
A Software Developer was asked 7mo agoQ3. What are abstraction and interfaces in Java?
Jio Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2025 Info Edge (India) Ltd.

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits