مسیریابی در هزارتو (عقبگرد)

از گوشه‌ی بالا-چپ تا گوشه‌ی پایین-راست راه پیدا می‌کند: جلو می‌رود و هر جا بن‌بست بود علامت می‌زند و عقب برمی‌گردد.

هزارتو یک جدول است: 0 خانه‌ی باز و 1 دیوار. از گوشه‌ی بالا-چپ شروع می‌کنیم و به ترتیب راست، پایین، چپ و بالا را امتحان می‌کنیم:

ورودی:

هزارتوی ۵×۵؛ اول شاخه‌ی سمت راست امتحان می‌شود و به بن‌بست می‌رسد (x)، بعد راه پایین تا خروجی می‌رود (o).

def solve_maze(grid):
# 0 is open and 1 is a wall; find a way from the top-left to the bottom-right corner.
rows, cols = len(grid), len(grid[0])
board = [["█" if cell else "·" for cell in row] for row in grid]
if grid[0][0] or grid[rows - 1][cols - 1]:
return False
return walk(board, 0, 0, rows, cols)
def walk(board, r, c, rows, cols):
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != "·":
return False
board[r][c] = "o"
if r == rows - 1 and c == cols - 1:
return True
for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
if walk(board, r + dr, c + dc, rows, cols):
return True
board[r][c] = "x"
return False

ناوردا: خانه‌های o همیشه یک مسیر پیوسته از شروع تا خانه‌ی فعلی‌اند و هر خانه حداکثر یک بار وارد می‌شود.

شروع اجرا

r—

c—

جدول هنوز خالی است.

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

نارنجی = در همین گام عوض شد

[0, 0, 0, 1, 0][1, 1, 0, 1, 0][0, 0, 0, 0, 0][0, 1, 1, 1, 1][0, 0, 0, 0, 0]

گام ۱ از ۲۳۰

توضیح

اگر خانه‌ی بعدی باز و ندیده باشد، واردش می‌شویم (o).
اگر از خانه‌ای هیچ راهی جلو نبود، آن را بن‌بست علامت می‌زنیم (x) و یک خانه عقب برمی‌گردیم.

این همان جست‌وجوی عمق‌اول روی گراف خانه‌هاست؛ پشته‌ی فراخوانی‌ها همان مسیر فعلی است.

هر خانه حداکثر یک بار وارد می‌شود: O(سطرها × ستون‌ها). مسیری که پیدا می‌شود لزوماً کوتاه‌ترین نیست؛ برای کوتاه‌ترین باید جست‌وجوی سطح‌اول زد.

جدول همان هزارتوست: █ دیوار، o مسیر فعلی و x بن‌بست‌ها. درخت فراخوانی‌ها شاخه‌های امتحان‌شده را نشان می‌دهد.