Practice/Meta/Maze Solver with Path Printing

Maze Solver with Path Printing

AI-Enabled CodingMust

Problem

You are building a navigation system for a robot moving through a grid-based environment. The grid contains open cells (represented by 0) and obstacles (represented by 1). Your task is to implement a pathfinding algorithm that determines a valid route from a starting position to a destination position.

The robot can move in four directions: up, down, left, and right. It cannot move diagonally or through obstacles. If a valid path exists, return it as a sequence of coordinates. If no path can be found, return an empty list.

Requirements

1. Implement a function that takes a 2D grid, a start position, and an end position
2. Find any valid path from start to end (you don't need to find the shortest path, though it's a bonus)
3. Return the path as a list of coordinate tuples/arrays in order from start to end
4. Return an empty list if no valid path exists
5. The robot can only move through cells containing 0 (not through walls marked with 1)
6. Movement is restricted to four directions: up, down, left, right (no diagonal movement)

Constraints

• 1 ≤ grid dimensions ≤ 100
• Grid values are either 0 (open) or 1 (wall)
• Start and end positions are guaranteed to be within grid boundaries
• Start and end positions are guaranteed to be open cells (value 0)
• Time complexity should be reasonable for the grid size (O(rows × cols) is acceptable)
• Space complexity should account for the visited cells and path storage

Examples

Example 1:

` Input: grid = [[0, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 1], [1, 0, 0, 0]] start = [0, 0] end = [3, 3]

Output: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (3, 3)]

Explanation: The path moves down the left side, then navigates right through the middle, avoiding walls. `

Example 2:

` Input: grid = [[0, 0, 0], [0, 1, 1], [0, 1, 0]] start = [0, 0] end = [2, 2]

Output: []

Explanation: The destination at (2, 2) is completely surrounded by walls, making it unreachable. `

Example 3:

` Input: grid = [[0]] start = [0, 0] end = [0, 0]

Output: [(0, 0)]

Explanation: Start and end are the same position, so the path contains only that single cell. `