用 Python 编写的检测 2D 网格中循环的程序

pythonserver side programmingprogramming更新于 2025/12/1 23:40:17

假设我们有一个 2D 字符数组，称为网格，大小为 m x n。我们必须检查是否可以在其中检测到循环。这里的循环是网格中长度为 4 或更长的路径，其起点和终点都相同。如果它具有与当前单元格相同的值，我们可以向四个方向移动(上、下、左或右)，并且我们不能重新访问某个单元格。

因此，如果输入如下

m	m	m	p
m	k	m	m
m	m	s	m
f	t	m	m

则输出为 True，因为绿色单元格正在形成循环。

要解决此问题，我们将遵循以下步骤 −

白色 := 0，灰色 := 1，黑色 := 2
R := 网格的行数
C := 网格的列数
color := 一个空映射，其默认值为 0
定义一个函数 dfs() 。这将需要 r、c、pr:= -1、pc:= -1
color[r,c] := GRAY
对于 di 中的每一对 (x,y)，执行
- (nr,nc) := (r+x,c+y)
- 如果 0 <= nr < R 且 0 <= nc < C 且 grid[r, c] 与 grid[nr, nc] 相同且 (nr, nc) 与 (pr, pc) 不同，则
  - 如果 color[nr,nc] 与 WHITE 相同，则
    - 如果 dfs(nr,nc,r,c) 为真，则
      - 返回 True
    - 否则，当 color[nr,nc] 与 GRAY 相同时，则
      - 返回 True
  - color[r,c] := BLACK
  - 返回False
  - 从主方法中，执行以下操作
  - 对于 0 到 R - 1 范围内的 r，执行以下操作
    - 对于 0 到 C - 1 范围内的 c，执行以下操作
      - 如果 color[r,c] 与 WHITE 相同，则
        
        如果 dfs(r,c) 为真，则
        
        返回 True
返回 False

示例

让我们看看下面的实现以便更好地理解

from collections import defaultdict
di = [(0,1),(1,0),(0,-1),(-1,0)]
def solve(grid):
   WHITE,GRAY,BLACK = 0 ,1 ,2
   R,C = len(grid),len(grid[0])

   color = defaultdict(int)

   def dfs(r,c,pr=-1,pc=-1):
      color[r,c] = GRAY
      for x,y in di:
         nr,nc = r+x,c+y
         if (0<=nr<R and 0<=nc<C and grid[r][c] == grid[nr][nc] and (nr,nc)!=(pr,pc)):
            if color[nr,nc]==WHITE:
               if dfs(nr,nc,r,c):
                  return True
            elif color[nr,nc] == GRAY:
               return True

      color[r,c] = BLACK
      return False

   for r in range(R):
      for c in range(C):
         if color[r,c] == WHITE:
            if dfs(r,c):
               return True
   return False
matrix = [["m","m","m","p"],["m","k","m","m"],["m","m","s","m"],["f","m","m","m"]]
print(solve(matrix))