資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 Python 查詢從矩陣的一個單元格移動到另一個單元格所需的最小步數
假設我們有一個 N x N 矩陣 M，其中填充了 1、0、2、3。我們必須找到從源單元格移動到目標單元格所需的最小步數。只能經過空白單元格，可以向上、下、右、左移動。
值為 1 的單元格表示源。
值為 2 的單元格表示目標。
值為 3 的單元格表示空白單元格。
值為 0 的單元格表示障礙物。
只有一個源單元格和一個目標單元格。從源單元格到達目標單元格可能有多條路徑。矩陣中的每次移動都算作“1”。
因此，如果輸入如下所示：
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
則輸出為 5，
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
從起點到終點，綠色路徑是最短的。
為了解決這個問題，我們將遵循以下步驟：
nodes := order * order + 2
g := 一個具有“nodes”個頂點的空圖
k := 1
對於 i 從 0 到 order 的範圍：
對於 j 從 0 到 order 的範圍：
如果 mat[i, j] 不等於 0，則
如果 is_ok(i, j + 1, mat) 不為零，則
在 g 的 k 和 k + 1 節點之間建立一條邊
如果 is_ok(i, j - 1, mat) 不為零，則
在 g 的 k 和 k - 1 節點之間建立一條邊
如果 j < order - 1 且 is_ok(i + 1, j, mat) 不為零，則
在 g 的 k 和 k + order 節點之間建立一條邊
如果 i > 0 且 is_ok(i - 1, j, mat) 不為零，則
在 g 的 k 和 k - order 節點之間建立一條邊
如果 mat[i, j] 等於 1，則
src := k
如果 mat[i, j] 等於 2，則
dest := k
k := k + 1
返回從 g 中的 src 到 dest 執行廣度優先搜尋 (BFS) 的結果
示例
讓我們看看下面的實現，以便更好地理解：
class Graph: def __init__(self, nodes): self.nodes = nodes self.adj = [[] for i in range(nodes)] def insert_edge (self, src , dest): self.adj[src].append(dest) self.adj[dest].append(src) def BFS(self, src, dest): if (src == dest): return 0 level = [-1] * self.nodes queue = [] level[src] = 0 queue.append(src) while (len(queue) != 0): src = queue.pop() i = 0 while i < len(self.adj[src]): if (level[self.adj[src][i]] < 0 or level[self.adj[src][i]] > level[src] + 1 ): level[self.adj[src][i]] = level[src] + 1 queue.append(self.adj[src][i]) i += 1 return level[dest] def is_ok(i, j, mat): global order if ((i < 0 or i >= order) or (j < 0 or j >= order ) or mat[i][j] == 0): return False return True def get_min_math(mat): global order src , dest = None, None nodes = order * order + 2 g = Graph(nodes) k = 1 for i in range(order): for j in range(order): if (mat[i][j] != 0): if (is_ok (i , j + 1 , mat)): g.insert_edge (k , k + 1) if (is_ok (i , j - 1 , mat)): g.insert_edge (k , k - 1) if (j < order - 1 and is_ok (i + 1 , j , mat)): g.insert_edge (k , k + order) if (i > 0 and is_ok (i - 1 , j , mat)): g.insert_edge (k , k - order) if(mat[i][j] == 1): src = k if (mat[i][j] == 2): dest = k k += 1 return g.BFS (src, dest) order = 4 mat = [[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]] print(get_min_math(mat))
輸入
[[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]
輸出
0
更新於：2020年8月20日
294 次瀏覽
廣告