在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

以上是 在Python中的二进制矩阵中找到最大路径长度 的全部内容, 来源链接: utcz.com/z/354065.html

回到顶部