在Python中检测2D网格中的循环的程序

假设我们有一个大小为m x n的字符2D数组称为网格。我们必须检查是否可以在其中检测到循环。这里的循环是网格中长度为4或更长的以相同位置为起点和终点的路径。我们可以沿着四个方向（上，下，左或右）移动，如果具有当前单元的相同值，我们就无法回访一些单元。

因此，如果输入如下：

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

那么输出将为True，因为绿色单元格正在形成循环。为了解决这个问题，我们将遵循以下步骤：

WHITE := 0, GRAY := 1, BLACK := 2
R := 网格的行数
C := 网格的列数
颜色 := 一个默认值为0的空映射
定义一个函数dfs()。这将采取r、c、pr:=-1、pc:=-1
颜色[r,c] := GRAY
对于每对（x，y），做以下操作：
- （nr，nc）:=（r+x，c+y）
- 如果0 ≤ nr < R and 0 ≤ nc < C and grid [r，c]与grid [nr，nc]相同且（nr，nc）与（pr，pc）不同，则
  - 如果color [nr，nc]与WHITE相同，则
  - 如果dfs（nr，nc，r，c）为true，则
    - 返回True
  - 否则，当color [nr，nc]等于GRAY时，
    - 返回True
  - 颜色[r，c] := BLACK
  - 返回False
  - 从主方法开始，做以下操作
  - 对于r在范围0到R-1，做以下操作
  - 对于c在范围0到C-1，做以下操作
    - 如果color [r，c]与WHITE相同，则
    - 如果dfs（r，c）为true，则
      - 返回True
- 返回False

示例

让我们看下面的实现以获得更好的理解

“`python 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])

<pre><code> 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))
</code></pre>

<pre><code class="line-numbers">## 输入
“`python 7, [5,1,4,3]“`

## 输出
“`python True