Kintsugi Zuihitsu

Reading Settings

AA
↔↔↔

Can You Exit the Maze

2 min read

Can You Exit the Maze

Challenge Difficulty: Hard | Estimated completion time: ~45 minutes

You are given a 2D matrix representing a maze, where 0 is a walkable path and 1 is a wall.

You start at the top-left corner and you have to reach the bottom-right corner.

Write a function that returns true if a path exists.

You can only move up, down, left and right. You cannot move diagonally.

Examples

canExit([
  [0, 1, 1, 1, 1, 1, 1],
  [0, 0, 1, 1, 0, 1, 1],
  [1, 0, 0, 0, 0, 1, 1],
  [1, 1, 1, 1, 0, 0, 1],
  [1, 1, 1, 1, 1, 0, 0]
])
output = True
 
canExit([
  [0, 1, 1, 1, 1, 1, 1],
  [0, 0, 1, 0, 0, 1, 1],
  [1, 0, 0, 0, 0, 1, 1],
  [1, 1, 0, 1, 0, 0, 1],
  [1, 1, 0, 0, 1, 1, 1]
])
output = False
# This maze only has dead ends!
 
canExit([
  [0, 1, 1, 1, 1, 0, 0],
  [0, 0, 0, 0, 1, 0, 0],
  [1, 1, 1, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 0],
  [1, 1, 1, 1, 1, 1, 1]
]) 
output = False
# Exit only one block away, but unreachable!
 
canExit([
  [0, 1, 1, 1, 1, 0, 0],
  [0, 0, 0, 0, 1, 0, 0],
  [1, 1, 1, 0, 0, 0, 0],
  [1, 0, 0, 0, 1, 1, 0],
  [1, 1, 1, 1, 1, 1, 0]
])
output = True

Graph View