資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 Python 中查詢銀行中警衛的最短距離
假設我們有一個矩陣，其中填充了三個字母“O”、“G”和“W”，其中“O”表示銀行中的開放空間，“G”表示警衛，“W”表示牆壁，我們必須替換矩陣中所有“O”，使其相對於一個警衛的最短距離，我們不能穿過任何牆壁。在輸出矩陣中，警衛被替換為 0，牆壁被替換為 -1。
因此，如果輸入類似於
| O | O | O | O | G |
| O | O | O | W | O |
| O | W | O | O | O |
| G | W | W | W | O |
| O | O | O | O | G |
那麼輸出將是
| 3 | 3 | 2 | 1 | 0 |
| 2 | 3 | 3 | -1 | 1 |
| 1 | -1 | 4 | 3 | 2 |
| 0 | -1 | -1 | -1 | 1 |
| 1 | 2 | 2 | 1 | 0 |
為了解決這個問題，我們將遵循以下步驟：
M := 5
N := 5
dir_row := [-1, 0, 1, 0]
dir_col := [0, 1, 0, -1]
定義一個函式 is_ok()。這將接收 i、j
如果 (i 在 0 和 M 範圍內) 或 (j 在 0 和 j N 範圍內)，則
返回 False
返回 True
定義一個函式 isSafe()。這將接收 i、j、matrix、result
如果 matrix[i, j] 不是 'O' 或 result[i, j] 不是 -1，則
返回 False
返回 True
定義一個函式 calculate_dist()。這將接收 matrix
result := 建立一個 M x N 階矩陣並填充 -1
定義一個雙端佇列 q
對於 i 從 0 到 M，執行
對於 j 從 0 到 N，執行
result[i, j] := -1
如果 matrix[i, j] 與 'G' 相同，則
pos := [i, j, 0]
將 pos 插入到 q 的左側
result[i, j] := 0
當 q 的大小 > 0 不為零時，執行
curr := 從 q 中刪除最後一個元素
x、y、dist := curr[0]、curr[1]、curr[2]
對於 i 從 0 到 3，執行
如果 is_ok(x + dir_row[i], y + dir_col[i]) 不為零且 isSafe(x + dir_row[i], y + dir_col[i], matrix, result) 不為零，則
result[x + dir_row[i], y + dir_col[i]] := dist + 1
pos := [x + dir_row[i], y + dir_col[i], dist + 1]
將 pos 插入到 q 的左側
對於 i 從 0 到 M，執行
對於 j 從 0 到 N，執行
顯示 result[i, j]
轉到下一行
示例
讓我們看看以下實現以更好地理解：
from collections import deque as queue M = 5 N = 5 dir_row = [-1, 0, 1, 0] dir_col = [0, 1, 0, -1] def is_ok(i, j): if ((i < 0 or i > M - 1) or (j < 0 or j > N - 1)): return False return True def isSafe(i, j,matrix, result): if (matrix[i][j] != 'O' or result[i][j] != -1): return False return True def calculate_dist(matrix): result = [[ -1 for i in range(N)]for i in range(M)] q = queue() for i in range(M): for j in range(N): result[i][j] = -1 if (matrix[i][j] == 'G'): pos = [i, j, 0] q.appendleft(pos) result[i][j] = 0 while (len(q) > 0): curr = q.pop() x, y, dist = curr[0], curr[1], curr[2] for i in range(4): if is_ok(x + dir_row[i], y + dir_col[i]) and isSafe(x + dir_row[i], y + dir_col[i], matrix, result) : result[x + dir_row[i]][y + dir_col[i]] = dist + 1 pos = [x + dir_row[i], y + dir_col[i], dist + 1] q.appendleft(pos) for i in range(M): for j in range(N): if result[i][j] > 0: print(result[i][j], end=" ") else: print(result[i][j],end=" ") print() matrix = [['O', 'O', 'O', 'O', 'G'], ['O', 'O', 'O', 'W', 'O'], ['O', 'W', 'O', 'O', 'O'], ['G', 'W', 'W', 'W', 'O'], ['O', 'O', 'O', 'O', 'G']] calculate_dist(matrix)
輸入
[['O', 'O', 'O', 'O', 'G'], ['O', 'O', 'O', 'W', 'O'], ['O', 'W', 'O', 'O', 'O'], ['G', 'W', 'W', 'W', 'O'], ['O', 'O', 'O', 'O', 'G']]
輸出
3 3 2 1 0 2 3 3 -1 1 1 -1 4 3 2 0 -1 -1 -1 1 1 2 2 1 0
114 次檢視
