Python程式檢查矩陣中某些元素是否形成迴圈

假設我們有一個二維矩陣。我們需要檢查是否可以從某個單元格開始，然後移動到具有相同值的相鄰單元格（上、下、左、右），並回到相同的起始單元格。我們不能重新訪問我們上次訪問過的單元格。

因此，如果輸入類似於

2
2
2
1
2
1
2
1
2
2
2
1

則輸出將為 True，因為我們可以按照 2 來形成一個迴圈。

為了解決這個問題，我們將遵循以下步驟：

  • R := 矩陣的行數
  • C := 矩陣的列數
  • vis := 建立一個大小為 R x C 的矩陣並填充 False
  • 定義一個函式 dfs()。它將接收根節點
  • stack := 一個包含兩個元素的棧：根節點和 null
  • vis[root[0], root[1]] := True
  • 當 stack 不為空時，執行以下操作：
    • [v, prev] := stack 的頂部元素，並將其彈出
    • 對於 v 的每個鄰居 w，執行以下操作：
      • 如果 w 不等於 prev，則
        • 如果 vis[w[0], w[1]] 為假，則
          • vis[w[0], w[1]] := True
          • 將 [w, v] 推入 stack
      • 否則，
        • 返回 True
  • 返回 False
  • 在主方法中執行以下操作：
  • 對於 i 從 0 到 R - 1，執行以下操作：
    • 對於 j 從 0 到 C - 1，執行以下操作：
      • 如果 vis[i, j] 為假，則
        • 如果 dfs((i, j)) 為真，則
          • 返回 True
  • 返回 False

讓我們看看以下實現以更好地理解：

示例

線上演示

class Solution:
   def solve(self, matrix):
      R = len(matrix)
      C = len(matrix[0])

      def get_neighbors(i, j):
         val = matrix[i][j]
         for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
            if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == val:
               yield ii, jj

      vis = [[False] * C for _ in range(R)]

      def dfs(root):
         stack = [(root, None)]
         vis[root[0]][root[1]] = True
         while stack:
            v, prev = stack.pop()
            for w in get_neighbors(*v):
               if w != prev:
                  if not vis[w[0]][w[1]]:
                     vis[w[0]][w[1]] = True
                     stack.append((w, v))
                  else:
                     return True
         return False

      for i in range(R):
         for j in range(C):
            if not vis[i][j]:
               if dfs((i, j)):
                  return True
      return False
     
ob = Solution()
matrix = [
   [2, 2, 2, 1],
   [2, 1, 2, 1],
   [2, 2, 2, 1]
]
print(ob.solve(matrix))

輸入

[  
[2, 2, 2, 1],  
[2, 1, 2, 1],  
[2, 2, 2, 1] ]

輸出

True

更新於: 2020年12月3日

155 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告