Wie in polynomialer Zeit zu lösen Rat in Maze Puzzle?

Question

I gefragt wurde kürzlich this question in einem Interview:

ein Labyrinth als N * N binäre Matrix von Blöcken gegeben, in dem Quellenblock das obere linke meist Block dh, maze [0] [0] und Ziel Block ist unteren rechten Block, dh, Labyrinth [N-1] [N-1]. Eine Ratte startet von der Quelle und muss das Ziel erreichen. Die Ratte kann sich nur in zwei Richtungen bewegen: vorwärts und abwärts. (oder 4 im fortgeschrittenen Problem). In der Labyrinth-Matrix bedeutet 0 , dass der Block eine Sackgasse ist und 1 bedeutet, dass der Block im Pfad von der Quelle zum Ziel verwendet werden kann.

Meine Antwort war die im Link erwähnte, die Backtracking verwendet. High level Pseudo-Code aus dem Link:

If destination is reached 
    print the solution matrix 
Else 
    a) Mark current cell in solution matrix as 1. 
    b) Move forward in horizontal direction and recursively check if this 
     move leads to a solution. 
    c) If the move chosen in the above step doesn't lead to a solution 
     then move down and check if this move leads to a solution. 
    d) If none of the above solutions work then unmark this cell as 0 
     (BACKTRACK) and return false. 

Der Interviewer ganz durch meine Antwort überrascht war, und war offenbar ein Polynom Zeit Lösung zu erwarten.

Gibt es eine polynomielle Zeitlösung für dieses Problem?

Answer 1

Dies kann in linearer Zeit unter Verwendung BFS gelöst werden.

Das Problem ist eigentlich ein Graph, wo alle Zellen Vertices sind und eine mögliche Bewegung von Zellen die Kanten sind. Sie suchen den kürzesten Pfad von einer Quelle zum Ziel, was genau BFS tut.

(Beachten Sie, dass in vereinfachter Problem mit nur „down“ und „rechts“ erlaubt hat gültige Pfad gleich lang ist. Das ist aber nicht wahr für das komplexere Problem mit 4 erlaubt Richtungen)

den generieren tatsächlichen Pfad, müssen Sie den Pfad verfolgen, indem Sie sich das übergeordnete Element jedes erkundeten Knotens merken. Dies wird in der Frage diskutiert: How can I find the actual path found by BFS?