在 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
- 对于j从0到C – 1,执行以下操作:
- 返回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