Rat Maze Traversal | Dataford Interview Questions

Rat Maze Traversal

MediumPython

Problem

An Airtel network planning grid is represented by a rectangular matrix. A value of 1 is an open cell, and 0 is blocked. Starting at the top-left cell, (0, 0), reach the bottom-right cell, (rows - 1, cols - 1) by moving up, down, left, or right.

Implement solve_rat_maze(maze) using both DFS and BFS. Return the paths found by each algorithm. DFS may return any valid path, while BFS must return a shortest path. Represent each path as an ordered list of [row, column] coordinates. Return an empty list when no path exists.

Use the deterministic neighbor order: down, right, up, left. Both algorithms must avoid revisiting cells.

Formal Specification

Input: maze, a non-empty rectangular list of lists containing only 0 and 1.
Output: A dictionary with keys dfs and bfs. Each value is a coordinate path, or [] if the destination cannot be reached.
The start and destination cells must be included when a path exists.

Constraints

1 <= rows, cols <= 1000
The matrix is rectangular
maze[r][c] is either 0 or 1
Movement is allowed only up, down, left, or right
The path may not visit a cell more than once

Function Signature

def solve_rat_maze(maze):

Use the deterministic neighbor order: down, right, up, left. Both algorithms must avoid revisiting cells.

Formal Specification

Input: maze, a non-empty rectangular list of lists containing only 0 and 1.
Output: A dictionary with keys dfs and bfs. Each value is a coordinate path, or [] if the destination cannot be reached.
The start and destination cells must be included when a path exists.