資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：檢查走出迷宮所需的指南針使用次數是否足夠
假設我們正在玩一個遊戲，我們被困在一個迷宮裡。我們必須找到走出迷宮的方法。迷宮可以表示為一個n x m矩陣，其中n是行數，m是列數。矩陣的每個單元格/元素包含'O'、'D'、'S'或'-'中的任何一個符號。'O'表示路徑被阻塞，'D'是迷宮的出口，'S'是我們的起始位置，而'-'表示我們可以透過該路徑移動。我們可以自由地穿過任何標記為'-'的單元格。現在，我們還有一個指南針，可以使用它找到迷宮的出口路徑（'D'單元格）。當我們需要找到方向時，必須使用指南針。但是，我們最多隻能使用指南針k次。給定迷宮作為矩陣和可以使用指南針的次數；我們必須找出在只使用了這麼多次數指南針的情況下是否可以走出迷宮。如果可能，則返回True，否則返回False。
因此，如果輸入類似於grid =
| - | O | - | O | - | - | - | - | - | - | O |
| - | O | D | - | O | - | O | O | O | - | O |
| - | O | O | - | O | - | O | O | O | - | O |
| - | O | O | - | O | - | O | S | - | - | - |
| - | - | - | - | - | - | O | O | O | O | - |
n = 4, m = 11, k = 3；則輸出將為True。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式path_search()。這將接收curr_pos、grid、total_rows、total_cols、k、predecessor。
x:= curr_pos的x值
y:= curr_pos的y值
如果grid[x, y]與"*"相同，則
如果k與0相同，則
返回True
否則，
返回False
否則，
parent := predecessor[curr_pos]
succ_pos := 從succesor_positions(curr_pos, grid, total_rows, total_cols, parent)的返回值建立一個新列表
use_compass := 如果succ_pos的大小> 1，則為True
對於succ_pos中的每個位置，執行：
predecessor[position] := curr_pos
如果use_compass不為零，則
path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
- 否則，
path_search(position, grid, total_rows, total_cols, k, predecessor)
定義一個函式succesor_positions()。這將接收curr_pos、grid、total_rows、total_cols、parent。
x:= curr_pos的x值
y:= curr_pos的y值
succ_pos := 一個新列表
如果y > 0，則
left := x, y - 1
將left插入succ_pos的末尾
如果y < total_cols - 1，則
right := x, y + 1
將right插入succ_pos的末尾
如果x > 0，則
up := x - 1, y
將up插入succ_pos的末尾
如果x < total_rows - 1，則
down := x + 1, y
將down插入succ_pos的末尾
如果對於succ_pos中的每個位置，grid[position[0], pos[1]]
不與"X"相同且pos不與parent相同，則：
返回滿足條件的succ_pos中的元素
現在執行以下操作：
curr_pos := 一個新的空對
對於每個索引i，grid中的每一行item，執行：
對於每個索引j，行中的每個元素item，執行：
如果元素與'M'相同，則
curr_pos := 一個包含i, j的新對
predecessor := 一個新的對映，其中curr_pos最初為Null
path_search(curr_pos, grid, n, m, k, predecessor)
原始碼 (Python)
讓我們看看下面的實現，以便更好地理解：
def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor):
x, y = curr_pos
if grid[x][y] == "D":
if k == 0:
print('True')
else:
print('False')
else:
parent = predecessor[curr_pos]
succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent))
use_compass = len(succ_pos) > 1
for position in succ_pos:
predecessor[position] = curr_pos
if use_compass:
path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
else:
path_search(position, grid, total_rows, total_cols, k, predecessor)
def succesor_positions(curr_pos, grid, total_rows, total_cols, pred):
x, y = curr_pos
succ_pos = []
if y > 0:
left = (x, y - 1)
succ_pos.append(left)
if y < total_cols - 1:
right = (x, y + 1)
succ_pos.append(right)
if x > 0:
up = (x - 1, y)
succ_pos.append(up)
if x < total_rows - 1:
down = (x + 1, y)
succ_pos.append(down)
return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos)
def solve(grid, n, m, k):
curr_pos = ()
for i, row in enumerate(grid):
for j, element in enumerate(row):
if element == 'S':
curr_pos = (i, j)
path_search(curr_pos, grid, n, m, k, predecessor = {curr_pos: None})
grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']]
solve(grid, 4, 11, 3)輸入
grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'], ['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'], ['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'], ['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3
輸出
True
79 次瀏覽
