数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 检测二维网格中循环的程序
假设我们有一个大小为 m x n 的字符二维数组，称为网格。我们必须检查是否可以在其中检测到循环。这里，循环是指网格中长度为 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 := 网格的列数
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))
输入
7, [5,1,4,3]
输出
True
更新于: 2021年10月6日
178 次查看
广告