LC: 499. The Maze III

Question

The Essence

Details and Solutions

499. The Maze III:

The Essence: It is also a little bit different than the usual DFS problems as you cannot stop and change direction until you encounter a wall or the destination.

It is important to note that, you have to decide if DFS can pass over the next cell, not the current cell. For the case in the image; you must pass at the first encounter but you have to stop after another turn of DFS (and in a different direction.)

IMG-1626

Details:

• You can use the classical DFS method:

  https://github.com/spiralgo/algorithms/pull/282

• You can use the Dijkstra'S algorithm as well:

  https://github.com/spiralgo/algorithms/pull/286