資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 檢測二維網格中迴圈的程式
假設我們有一個大小為 m x n 的字元二維陣列，稱為網格。我們必須檢查是否可以在其中檢測到迴圈。這裡，迴圈是指網格中長度為 4 或更長的路徑，該路徑在相同的位置開始和結束。我們可以在四個方向（上、下、左或右）移動，如果它與當前單元格的值相同，並且我們不能重新訪問某些單元格。
因此，如果輸入如下所示：
| m | m | m | p |
| m | k | m | m |
| m | m | s | m |
| f | t | m | m |
那麼輸出將為 True，因為綠色單元格形成了迴圈。
為了解決這個問題，我們將遵循以下步驟：
WHITE := 0，GRAY := 1，BLACK := 2
R := 網格的行數
C := 網格的列數
color := 一個空對映，其預設值為 0
定義一個函式 dfs()。這將接收 r、c、pr:= -1、pc:= -1
color[r,c] := GRAY
對於 di 中的每一對 (x,y)，執行以下操作：
(nr,nc) := (r+x,c+y)
如果 0 <= nr < R 且 0 <= nc < C 且 grid[r, c] 與 grid[nr, nc] 相同，並且 (nr, nc) 與 (pr, pc) 不相同，則：
如果 color[nr,nc] 與 WHITE 相同，則：
如果 dfs(nr,nc,r,c) 為真，則：
返回 True
否則，當 color[nr,nc] 與 GRAY 相同時，則：
返回 True
color[r,c] := BLACK
返回 False
從主方法中執行以下操作：
對於從 0 到 R - 1 的範圍內的 r，執行以下操作：
對於從 0 到 C - 1 的範圍內的 c，執行以下操作：
如果 color[r,c] 與 WHITE 相同，則：
如果 dfs(r,c) 為真，則：
返回 True
返回 False
示例
讓我們看看以下實現以獲得更好的理解
from collections import defaultdict di = [(0,1),(1,0),(0,-1),(-1,0)] def solve(grid): WHITE,GRAY,BLACK = 0 ,1 ,2 R,C = len(grid),len(grid[0]) color = defaultdict(int) def dfs(r,c,pr=-1,pc=-1): color[r,c] = GRAY for x,y in di: nr,nc = r+x,c+y if (0<=nr<R and 0<=nc<C and grid[r][c] == grid[nr][nc] and (nr,nc)!=(pr,pc)): if color[nr,nc]==WHITE: if dfs(nr,nc,r,c): return True elif color[nr,nc] == GRAY: return True color[r,c] = BLACK return False for r in range(R): for c in range(C): if color[r,c] == WHITE: if dfs(r,c): return True return False matrix = [["m","m","m","p"],["m","k","m","m"],["m","m","s","m"],["f","m","m","m"]] print(solve(matrix))
輸入
7, [5,1,4,3]
輸出
True
更新於: 2021年10月6日
178 次檢視
廣告