Python Breite-erste Suche Matrix Druckpfad

Question

Ich habe diese Codezeile, die testet, ob es einen Pfad in einem Labyrinth gibt, das durch eine Matrix repräsentiert wird. Wie drucke ich den Pfad am Ende, nachdem ich festgestellt habe, ob es einen Pfad gibt oder nicht. Ich habe versucht, einen Stapel zu machen, aber ich bin mir nicht sicher, wie es weitergehen soll.

from queue import Queue 
maze=open(input()) 
matrix=maze.readlines() 
matrix=[i.strip() for i in matrix] 
matrix=[i.split() for i in matrix] 
numrows, numcols = len(matrix), len(matrix[0]) 
q=Queue() 
row=0 
col=0 
q.put((row,col)) 
while not q.empty(): 
    row, col = q.get() 
    if col+1 < numcols and matrix[row][col+1] == "0": 
     q.put((row, col+1)) 
     matrix[row][col+1] = "2" 
    if row+1 < numrows and matrix[row+1][col] == "0": 
     q.put((row+1, col)) 
     matrix[row+1][col] = "3" 
    if 0 <= col-1 and matrix[row][col-1] == "0": 
     q.put((row, col-1)) 
     matrix[row][col-1] = "4" 
    if 0 <= row-1 and matrix[row-1][col] == "0": 
     q.put((row-1, col)) 
     matrix[row-1][col] = "5" 
row,col=numrows-1,numcols-1 
var=matrix[row][col] 
if var=="0": 
    print ("There is no path.") 
else: 
    print ("There is a path.") 

Hier ist eine Probenmatrix:

0 0 0 0 1 0 0 0 
0 1 1 0 1 0 1 0 
0 1 0 0 1 0 1 0 
0 0 0 1 0 0 1 0 
0 1 0 1 0 1 1 0 
0 0 1 1 0 1 0 0 
1 0 0 0 0 1 1 0 
0 0 1 1 1 1 0 0 

Answer 1

Weil Sie BFS verwenden Sie den Pfad zu finden, der Endanflug nicht der kürzeste Weg vom Startpunkt zum Zielpunkt sein, und tatsächlich, Sie können nur das Ergebnis erhalten, welcher Punkt mit dem Startpunkt verbunden ist.

Um einen genauen Pfad zu erhalten, können Sie mithilfe von DFS einen Pfad suchen und einen Stack verwenden, um die besuchten Punkte zu speichern, oder Dijkstra verwenden, um den kürzesten Pfad vom Startpunkt zum Endpunkt zu finden.

Hier ist eine einfache DFS-Funktion, die in Zeichen dargestellt wird 2

suc = 0 

def dfs(row, col): 
    global suc 
    if suc == 1: 
     return 
    matrix[row][col] = "2" 

    if (row, col) == (numrows - 1, numcols - 1): 
     print("Success") 
     suc = 1 

    if col + 1 < numcols and matrix[row][col + 1] == "0": 
     dfs(row, col + 1) 

    if row + 1 < numrows and matrix[row + 1][col] == "0": 
     dfs(row + 1, col) 

    if 0 <= col - 1 and matrix[row][col - 1] == "0": 
     dfs(row, col - 1) 

    if 0 <= row - 1 and matrix[row - 1][col] == "0": 
     dfs(row - 1, col) 


maze = open(input()) 
matrix = maze.readlines() 
matrix = [i.strip() for i in matrix] 
matrix = [i.split() for i in matrix] 
numrows, numcols = len(matrix), len(matrix[0]) 

dfs(0, 0) 

var = matrix[numrows - 1][numcols - 1] 

for m in matrix: 
    print(m) 

if var == "0": 
    print("There is no path.") 
else: 
    print("There is a path.") 

Answer 2

Hier ist Rekursion und der Pfad verwendet eine ziemlich einfache Art und Weise den Weg zu finden, um es rückwärts von der Ausfahrt zu verfolgen. Sie können dies umkehren, indem Sie die Züge auf einen Stapel speichern.

Um es einfacher zu sehen, habe ich Ihren Code leicht geändert, um N, S, E, W in die Matrix (für Nord, Süd, Ost, West) zu setzen. Um diese Richtungszeichen in (Zeilen-, Spalten-) Schritten zu dekodieren, benutze ich ein Wörterbuch.

from queue import Queue 

maze='''\ 
0 0 0 0 1 0 0 0 
0 1 1 0 1 0 1 0 
0 1 0 0 1 0 1 0 
0 0 0 1 0 0 1 0 
0 1 0 1 0 1 1 0 
0 0 1 1 0 1 0 0 
1 0 0 0 0 1 1 0 
0 0 1 1 1 1 0 0 
''' 

def show(matrix): 
    for line in matrix: 
     print(*line) 
    print() 

matrix=maze.splitlines() 
matrix=[i.strip() for i in matrix] 
matrix=[i.split() for i in matrix] 
numrows, numcols = len(matrix), len(matrix[0]) 

show(matrix) 

q=Queue() 
row=0 
col=0 
q.put((row,col)) 
while not q.empty(): 
    row, col = q.get() 
    if col+1 < numcols and matrix[row][col+1] == "0": 
     q.put((row, col+1)) 
     matrix[row][col+1] = "W" 
    if row+1 < numrows and matrix[row+1][col] == "0": 
     q.put((row+1, col)) 
     matrix[row+1][col] = "N" 
    if 0 <= col-1 and matrix[row][col-1] == "0": 
     q.put((row, col-1)) 
     matrix[row][col-1] = "E" 
    if 0 <= row-1 and matrix[row-1][col] == "0": 
     q.put((row-1, col)) 
     matrix[row-1][col] = "S" 
row,col=numrows-1,numcols-1 
var=matrix[row][col] 

show(matrix) 

if var=="0": 
    print ("There is no path.") 
    exit() 
else: 
    print ("There is a path.") 

# Trace the path 
step = {'N': (-1, 0), 'S': (1, 0), 'E': (0, 1), 'W': (0, -1)} 
while True: 
    print((row, col), 'go', var) 
    if row == 0 and col == 0: 
     break 
    r, c = step[var] 
    row += r 
    col += c 
    var = matrix[row][col] 

print('Home!') 

Ausgang

0 0 0 0 1 0 0 0 
0 1 1 0 1 0 1 0 
0 1 0 0 1 0 1 0 
0 0 0 1 0 0 1 0 
0 1 0 1 0 1 1 0 
0 0 1 1 0 1 0 0 
1 0 0 0 0 1 1 0 
0 0 1 1 1 1 0 0 

E W W W 1 S W W 
N 1 1 N 1 S 1 N 
N 1 E N 1 S 1 N 
N W W 1 S W 1 N 
N 1 N 1 S 1 1 N 
N W 1 1 S 1 E N 
1 N W W W 1 1 N 
E N 1 1 1 1 E N 

There is a path. 
(7, 7) go N 
(6, 7) go N 
(5, 7) go N 
(4, 7) go N 
(3, 7) go N 
(2, 7) go N 
(1, 7) go N 
(0, 7) go W 
(0, 6) go W 
(0, 5) go S 
(1, 5) go S 
(2, 5) go S 
(3, 5) go W 
(3, 4) go S 
(4, 4) go S 
(5, 4) go S 
(6, 4) go W 
(6, 3) go W 
(6, 2) go W 
(6, 1) go N 
(5, 1) go W 
(5, 0) go N 
(4, 0) go N 
(3, 0) go N 
(2, 0) go N 
(1, 0) go N 
(0, 0) go E 
Home! 

Answer 3

Als Variante zu @ 程 名 锐 's Beitrag, diese Implementierung eines DFS auch den ersten Pfad zurückkehren es gefunden hat. Und als allgemeinen Hinweis: Wenn Sie sich nicht darum kümmern, dass der Pfad optimal ist, wird Ihnen ein DFS normalerweise besser als ein BFS dienen.

Beachten Sie, dass wir auch sicherstellen müssen, nicht in Kreisen zu laufen, da dieses Diagramm kein Baum ist.

# for convenience 
matrix = [ 
    ["0", "0", "0", "0", "1", "0", "0", "0"], 
    ["0", "1", "1", "0", "1", "0", "1", "0"], 
    ["0", "1", "0", "0", "1", "0", "1", "0"], 
    ["0", "0", "0", "1", "0", "0", "1", "0"], 
    ["0", "1", "0", "1", "0", "1", "1", "0"], 
    ["0", "0", "1", "1", "0", "1", "0", "0"], 
    ["1", "0", "0", "0", "0", "1", "1", "0"], 
    ["0", "0", "1", "1", "1", "1", "0", "0"] 
] 
num_rows = len(matrix) 
num_cols = len(matrix[0]) 

# just to be a bit more flexible, could also be passed as a function argument 
goal_state = (num_rows - 1, num_cols - 1) 


def dfs(current_path): 
    # anchor 
    row, col = current_path[-1] 
    if (row, col) == goal_state: 
     return True 

    # try all directions one after the other 
    for direction in [(row, col + 1), (row, col - 1), (row + 1, col), (row - 1, col)]: 
     new_row, new_col = direction 
     if (0 <= new_row < num_rows and 0 <= new_col < num_cols and # stay in matrix borders 
       matrix[new_row][new_col] == "0" and     # don't run in walls 
       (new_row, new_col) not in current_path):    # don't run in circles 
      # try new direction 
      current_path.append((new_row, new_col)) 
      if dfs(current_path): # recursive call 
       return True 
      else: 
       current_path.pop() # backtrack 


# result a list of coordinates which should be taken in order to reach the goal 
result = [(0, 0)] 
if dfs(result): 
    print("Success!") 
    print(result) 
else: 
    print("Failure!") 

Drucke:

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (6, 1), (6, 2), (6, 3), (6, 4), (5, 4), (4, 4), (3, 4), (3, 5), (2, 5), (1, 5), (0, 5), (0, 6), (0, 7), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7)] 

Die erste (aber sicher nicht kürzeste) ein DFS richtigen Pfad mit den Wegfindung Vorlieben right -> left -> down -> up Begegnungen.