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

假设我们有一个二维矩阵。我们必须检查是否可以从某个单元格开始，然后移动具有相同值的相邻单元格（上，下，左，右），然后返回相同的起点。我们无法重新访问上次访问的单元。

所以，如果输入像

那么输出将为True，因为我们可以按照2s形成一个周期。

为了解决这个问题，我们将遵循以下步骤-

• R：=矩阵的行数

• C：=矩阵的列数

• vis：=制作大小为R x C的矩阵，并用False填充

• 定义一个功能dfs()。这将扎根

• stack：=具有两个元素root和null的堆栈

• vis [root [0]，root [1]]：= True

• 当堆栈不为空时，执行

• 如果w与上一个不同，则

• 除此以外，

• vis [w [0]，w [1]]：=真

• 将[w，v]推入堆栈

• 如果vis [w [0]，w [1]]为假，则

• 返回True

• [v，prev]：=堆栈的顶部元素，并从堆栈中弹出

• 对于v的每个邻居w

• 返回False

• 从主要方法执行以下操作：

• 对于介于0到R-1的i

• 如果vis [i，j]为假，则

• 返回True

• 如果dfs（(i,j)）为true，则

• 对于范围在0到C-1之间的j

• 返回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