在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("最大路径的长度是 " + str(findLargestPath(I)))

输出结果

最大路径的长度是 3