I’m just writing this to point out the differences between BFS and DFS here. To avoid confusions in using them.
Using BFS would mean that the robot or character in this case would have to teleport around on the map on each node he put in his queue.
The solution to this is actually a DFS where the character searches a path in a direction until it reaches some dead end and go back to the last branch point in the labyrinth… etc
Otherwhise in the case of BFS it would consume to much fuel to go back to the last unvisited node again.
See http://bryukh.com/labyrinth-algorithms/ for more information