Python程序检查矩阵中某些元素是否形成循环

假设我们有一个二维矩阵。我们需要检查是否可以从某个单元格开始，然后移动到具有相同值的相邻单元格（上、下、左、右），并回到相同的起始单元格。我们不能重新访问我们上次访问过的单元格。

因此，如果输入类似于

则输出将为 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

Arnab Chakraborty

更新于: 2020年12月3日

155 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习