Maze Solver (4 incremental tasks)
You are given an existing codebase for a maze solver that finds a path in a 2D grid. The maze is represented as a rectangular grid of characters.
-
#
= wall (cannot pass)
-
.
= open cell
-
S
= start (exactly one)
-
E
= exit (exactly one)
-
Movement is 4-directional (up/down/left/right) unless modified by special tiles below.
The solver should find a path (typically the shortest path) from S to E and then print the maze with the chosen path marked.
Task 1 — Fix printing bug
The code prints a derived representation (e.g., a path overlay / predecessor map). There is a bug: some cells to be printed can be null/empty.
-
Fix the printing logic so that it
checks for empty/null
.
-
When the printable value for a cell is empty/null, print
'*'
for that cell (instead of crashing or printing nothing).
Task 2 — Fix BFS visited initialization
The implementation uses BFS but has a bug related to visited.
-
Fix BFS so that at the start of the search it correctly handles the
visited
state (e.g., the start node should be marked visited at the right time to avoid revisiting / incorrect behavior).
Task 3 — Add a one-way chute tile
Add support for a one-way tile represented by > (a “chute” / one-way door).
-
Traversal must respect that
>
is
directional
.
-
Define the traversal rule clearly in your implementation (e.g., it can only be entered from one side and exited to the other, or it creates a directed edge consistent with the arrow direction).
-
Update BFS neighbor generation accordingly.
Task 4 — Add keys and doors (stateful reachability)
Add keys and doors:
-
Lowercase letters
a
–
z
are
keys
.
-
Uppercase letters
A
–
Z
are
doors
.
-
If you have collected key
a
, you may pass through door
A
(similarly for other letters).
-
Keys can be picked up by stepping on their cell.
Update the solver to find a valid path from S to E considering keys/doors. Pay attention to visited: reaching the same grid cell with different sets of keys should be treated as different states.
Output expectations
-
The program should print a solved maze (or clearly report that no path exists).
-
Be explicit about edge cases: no path, multiple keys, revisiting areas after picking up a key, interaction between
>
and doors/keys if applicable.
(You may assume reasonable grid sizes such as up to ~30×30 or ~100×100; optimize accordingly.)