Practice/Meta/Maze Pathfinding Algorithm

Maze Pathfinding Algorithm

AI-Enabled CodingMust

Problem

You are given a 2D grid representing a maze where each cell can either be passable or blocked by an obstacle. Your task is to find any valid path from a starting position to an ending position, navigating only through passable cells.

The grid is represented as a 2D array where:

• 0 represents a passable cell you can move through
• 1 represents an obstacle you cannot pass through

You can move in four directions: up, down, left, and right (no diagonal movement). Return a path as a list of coordinates from start to end, or an empty list if no path exists.

Requirements

1. Implement a function that takes a 2D maze array, a start coordinate, and an end coordinate
2. Find a valid path from start to end using only cells marked as 0
3. Return the path as a list of coordinate tuples/arrays in order from start to end
4. If no path exists, return an empty list
5. Movement is restricted to four directions: up, down, left, right
6. The start and end positions will always be passable cells (marked as 0)

Constraints

• Grid dimensions: 1 ≤ rows, cols ≤ 100
• Cell values are either 0 (passable) or 1 (obstacle)
• Start and end coordinates are valid positions within the grid
• Time complexity: Aim for O(rows × cols)
• Space complexity: O(rows × cols) for visited tracking and path storage

Examples

Example 1:

Input: maze = [[0, 0, 0], [0, 1, 0], [0, 0, 0]] start = (0, 0) end = (2, 2) Output: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)] Explanation: The path navigates around the obstacle at position (1, 1) by going right along the top row, then down the right column.

Example 2:

Input: maze = [[0, 1], [1, 0]] start = (0, 0) end = (1, 1) Output: [] Explanation: No path exists because all routes are blocked by obstacles.

Example 3:

Input: maze = [[0, 0, 0], [1, 1, 1], [0, 0, 0]] start = (0, 0) end = (0, 2) Output: [(0, 0), (0, 1), (0, 2)] Explanation: The shortest path goes directly along the top row.