• The maze is a 2D Grid of known width and height.

  • it's composed of squares: a Wall or a room.

    • You cannot walk into walls.

    • from each room you can only get to adjacent rooms. ( you can't teleport)

  • You can only know if a given square is wall if you are or were in a room adjacent to it.

  • You start at room (0,1)

  • You need to visit all rooms that are reachable in $k$ steps from the start. Visit as in physically walk to.

  • The performance of the algorithm is measured in terms of Total distance walked.

Naive approach: depth first search, but make sure to only revisit a node, if distance Left when last visited is less than current distance - 1.

what are better Algorithms to solve this problem?

  • $\begingroup$ One improvement would be to keep a "mental map" of the squares you visited and the adjacent ones, and instead of automatically revisiting a node with smaller left distance, first "mentally" visit it to see if any new room is reachable from there. If yes, revisit the node physically. If not, no point in trying. $\endgroup$ – Tassle Nov 19 '19 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.