##### Updated on February 10, 2019

## Problem

Given a 2D array which represents a maze, a start point, and an end point, find a path from the start point to the end point if it exists.

## Input

`maze`

: 2D boolean array of size greater than 1 x 1, where`False`

represents a wall (not traversable) and`True`

represents an empty space (traversable)`start`

: an object with x, y coordinates`end`

: an object with x, y coordinates

## Approach

The key to solving this problem is DFS. First look at the start point's adjacent blocks, and for each of those blocks, look at their adjacent blocks, etc. until you reach the coordinates of the end point.

An invalid block would be any block that has a value of `False`

in the `maze`

matrix, or any block with invalid coordinates (i.e. an x-coordinate of `-1`

means that it is not within the dimensions of the matrix). This will be the base case.

To look at each of the adjacent blocks, there could only be 4 possible choices: up, down, left, and right.

## Solution

```
import collections
Coordinate = collections.namedtuple("Coordinate", "x y")
def find_paths(maze, start, end):
path = []
def _dfs(curr):
if curr.x < 0 or curr.x >= len(maze) \
or curr.y < 0 or curr.y >= len(maze) \
or maze[curr.y][curr.x] == False:
return False
# This step can possibly lead to the end, so add it to the path
path.append(curr)
if curr == end:
return True
found = _dfs(Coordinate(x=curr.x-1, y=curr.y)) or \
_dfs(Coordinate(x=curr.x+1, y=curr.y)) or \
_dfs(Coordinate(x=curr.x, y=curr.y+1)) or \
_dfs(Coordinate(x=curr.x, y=curr.y-1))
if found:
return True
else:
# Undo the last step since this step does not lead to the end
del path[-1]
return False
if _dfs(start):
return path
return []
```