# Path Through a 2D Array

## The Problem

Given a 2D array of zeros and ones, where a zero indicates a position that can be reached and a one indicates a position that cannot, design an algorithm to find a path from the top left to the bottom right.

For example, given this input ...

0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0

... the following possible path exists (each step is marked with a +).

+ + + + 0 0 0 0 0 1 + 0 1 0 0 0 1 + 1 1 0 0 0 1 + 1 0 1 1 1 1 + + + +

After calculating a path, display it in the following format:

(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3) -> (4, 3) -> (4, 4) -> (4, 5) -> (4, 6)

## My Solution

My first instinct was to think of the matrix as a highly-connected graph. This was correct. But my subsequent instinct was that Djikstra's Algorithm would be appropriate. This was not correct because Djikstra's Algorithm requires edge weights, which this array does not have. Djikstra also tries to find the shortest path, which is more than is required here.

However, in thinking of Djikstra's Algorithm I remembered that Djikstra's Algorithm finds all (shortest) paths through the graph and then just picks the one to the targeted Node. That was a a key insight into how to solve the problem at hand.

I find it very difficult to think about the world as a 2D-array. Mapping into something more object-oriented helps me to think through the problem. I find it much easier to think "... and then we need to check which neighbors are reachable from that coordinate" than to have the analogous thought using lower-level primitives (x and y values in this case). A unique tuple of x and y represents a single, higher-order entity and I just need something to encapsulate that higher-order thing in order to solve higher-order problems such as finding a path from one coordinate to another. It's just how my brain works.

Once I came up with a simple object to encapsulate the coordinates in the array I found it easy to think through the path-finding algorithm.

My solution returned this path:

... which looks like this through the matrix:

+ + + + + 0 0 0 0 1 + + 1 0 0 0 1 + 1 1 0 0 0 1 + 1 0 1 1 1 1 + + + +

It isn't the same path as was proposed in the question. But since the question asks to show only that a path exists, and not necessarily the shortest path, this solution is OK.