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

假设我们有一个二维矩阵。我们必须检查是否可以从某个单元格开始，移动相邻单元格（上，下，左，右）的相同值，并回到相同的起点。我们不能重访一个我们曾经访问过的单元格。

因此，如果输入如下：

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

则输出为True，因为我们可以跟随2以形成一个循环。

要解决这个问题，我们按照以下步骤进行：

• R：矩阵的行数
• C：矩阵的列数
• vis：创建一个大小为R x C的矩阵，并使用False填充
• 定义一个函数dfs()。这将采取root作为输入参数
• stack：一个具有root和null两个元素的堆栈
• vis[root[0]， root[1]] = True
• 当stack不为空时，执行以下操作：
  • [v， prev] =堆栈的顶部元素，并从堆栈中弹出
  • 对于v的每个邻居w，请执行以下操作：
    • 如果w不同于prev，则
    • 如果vis[w[0]， w[1]]为false，则
      • vis[w[0]， w[1]] = True
      • 将[w， v]压入stack
    • 否则，
    • 返回True
• 返回False
• 从主方法中执行以下操作：
• 对于i从0到R – 1，执行以下操作：
  • 对于j从0到C – 1，执行以下操作：
    • 如果vis[i， j]为false，则
    • 如果dfs((i，j))为True，则
      • 返回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