Pythonのバイナリ行列で最大パス長を見つける

この問題では、各要素が0または1のいずれかでサイズmXnの正方行列mat[][]が与えられます。要素の値が1の場合、これは接続されていることを意味し、値が0の場合、これは接続されていません。私たちのタスクは、バイナリ行列で最大パス長を見つけることです。

問題の説明 −問題を解決するには、マトリックス上で最大の長さのパスを見つける必要があります。これは、マトリックス内の1つの要素すべてを意味します。パスを見つける前に、最大で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に変換した後に長さを見つけることです。まず深さ優先探索を使用してパスの長さを見つけ、次にすべてのパスの長さの最大値を返します。

効率的な解決策は、複数の変換を行う必要をなくし、最も有望な解決策を提供するものに落ち着くことです。 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