The Labyrinth - Puzzle discussion

Puzzles
76

With DFS it’s not guaranteed to find shortest path. BFS applied to pathfinding ~= Dijkstra ~= Flood Fill

BFS:

  • create queue / FIFO (Java = Queue / LinkedList) and put current position into it
  • while stack is not empty
    • get item from queue
    • check neighborhood (neighbor is ‘?’ = return success; neighbor is ‘.’ add neighbor to queue)
    • update board properly so you won’t visit same place twice and you can always tell what action u used at starting position in order to get here
  • if you have reached this point you haven’t found any ‘?’ -> you can’t reach any ?

You will most likely struggle a little bit. Maybe resolve more medium puzzles and come back here later? It was necessity for me. And don’t forget to debug print updated board so that you can see what is happening.

3 Likes