数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python中查找二元矩阵中的最大路径长度
在这个问题中，我们得到一个大小为 m X n 的方形矩阵 mat[][]，每个元素都是 0 或 1。如果一个元素的值为 1，则表示它已连接；如果值为 0，则表示它未连接。我们的任务是在二元矩阵中找到最大路径长度。
问题描述 − 为了解决这个问题，我们需要找到矩阵上最长的路径，这意味着矩阵中所有值为1的元素。在找到路径之前，我们将最多将一个 0 转换为 1。
让我们来看一个例子来理解这个问题：
输入
mat[][] = {{1, 0},
{0, 1}}输出
3
解释
We can convert 0 at index (0, 1) or (1, 0) to maximise the path length.
解决方案方法
一个简单的解决方案是通过在将每个 0 转换为 1 后查找路径长度来实现。我们将使用深度优先搜索来查找路径长度，然后返回所有路径长度中的最大值。
一个有效的解决方案是消除进行多次转换的需要，并选择一个能给出最有希望的解决方案的转换。我们将找到一个组，使得将一个 0 转换为 1 将返回最长的路径。
程序演示了我们解决方案的工作原理：
示例
def FindNeighbor(R, C, N):
for nr, nc in (((R - 1), C), ( (R + 1) , C), (R, (C - 1) ), (R, (C + 1) )):
if 0 <= nr < N and 0 <= nc < N:
yield nr, nc
def DFSTraversal(R, C, index, mat, N):
maxLen = 1
mat[R][C] = index
for nr, nc in FindNeighbor(R, C, N):
if mat[nr][nc] == 1:
maxLen += DFSTraversal(nr, nc, index)
return maxLen
def findLargestPath(mat):
N = len(mat)
maxPath = {}
index = 2
for i in range(N):
for j in range(N):
if mat[i][j] == 1:
maxPath[index] = DFSTraversal(i, j, index, mat, N)
index += 1
maxPathLen = max(maxPath.values() or [0])
for i in range(N):
for j in range(N):
if mat[i][j] == 0:
seen = {mat[nr][nc] for nr, nc in FindNeighbor(i, j, N) if mat[nr][nc] > 1}
maxPathLen = max(maxPathLen, 1 + sum(maxPath[i] for i in seen))
return maxPathLen
I = [[1, 0], [0, 1]]
print("The length of largest path is " + str(findLargestPath(I)))输出
The length of largest path is 3
更新于：2021年3月12日
219 次浏览
广告