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

在 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程