Pythonで島間の最短橋の距離を見つけるプログラム

バイナリ行列があるとします。ここで、0は水を表し、1は土地を表します。島は、4つの方向に1を接続するグループです。島は0（水）またはエッジに囲まれています。 2つの島を結ぶ最短の橋の長さを見つける必要があります。

したがって、入力が次のような場合

その場合、出力は1になります。これにより、（1,0）ポイントが（1,2）ポイントに接続されます。

これを解決するには、次の手順に従います-

• 行：=行列の行数

• col：=行列の列数

• 関数dfs（）を定義します。これにはi、j、sが必要です

• （i、j）がsの場合、

  • 戻る

• mat [i、j]が0と同じ場合、

  • 戻る

• （i、j）をsに挿入します

• i-1> =0の場合、

  • dfs（i-1、j、s）

• i + 1 <行の場合、

  • dfs（i + 1、j、s）

• j-1> =0の場合、

  • dfs（i、j-1、s）

• j + 1

  • dfs（i、j + 1、s）

• メインの方法から、次のようにします-

• 見た：=新しいセット

• 0から行までの範囲のiの場合、実行

  • 見たサイズが0より大きい場合、

    • ループから出てきます

  • 0からcolの範囲のjについては、次のようにします

    • mat [i、j]が1と同じ場合、

      • dfs（i、j、見た）

      • ループから出てきます

• q：=両端キュー

• 見られる土地ごとに、実行します

  • （i、j）：=土地

  • i --1> =0で、mat [i --1、j]が0と同じ場合、

    • qの最後に（i-1、j、1）を挿入します

  • i +1<行およびmat[i+ 1、j]が0と同じである場合、

    • qの最後に（i + 1、j、1）を挿入します

  • j --1> =0で、mat [i、j --1]が0と同じ場合、

    • qの最後に（i、j --1、1）を挿入します

  • j + 1

    • qの最後に（i、j + 1、1）を挿入します

• q> 0のサイズで、実行

  • （i、j、dist）：=qの左側のアイテム、およびqの左側からアイテムを削除

  • （i、j）が見られる場合、

    • 次のイテレーションに行く

  • 見たとおりに（i、j）をマーク

  • mat [i、j]が1と同じ場合、

    • return dist-1

  • i-1> =0の場合、

    • qの最後に（i-1、j、dist + 1）を挿入します

  • i + 1 <行がゼロ以外の場合、

    • qの最後に（i + 1、j、dist + 1）を挿入します

  • j-1> =0の場合、

    • qの最後に（i、j-1、dist + 1）を挿入します

  • j + 1

    • qの最後に（i、j + 1、dist + 1）を挿入します

例

理解を深めるために、次の実装を見てみましょう-

import collections
class Solution:
   def solve(self, mat):
      row = len(mat)
      col = len(mat[0])
      def dfs(i, j, s):
         if (i, j) in s:
            return
         if mat[i][j] == 0:
            return
         s.add((i, j))
         if i - 1 >= 0:
            dfs(i - 1, j, s)
         if i + 1 < row:
            dfs(i + 1, j, s)
         if j - 1 >= 0:
            dfs(i, j - 1, s)
         if j + 1 < col:
            dfs(i, j + 1, s)
      seen = set()
      for i in range(row):
         if len(seen) > 0:
            break
         for j in range(col):
            if mat[i][j] == 1:
               dfs(i, j, seen)
               break
      q = collections.deque()
      for land in seen:
         i, j = land
         if i - 1 >= 0 and mat[i - 1][j] == 0:
            q.append((i - 1, j, 1))
         if i + 1 < row and mat[i + 1][j] == 0:
            q.append((i + 1, j, 1))
         if j - 1 >= 0 and mat[i][j - 1] == 0:
            q.append((i, j - 1, 1))
         if j + 1 < col and mat[i][j + 1] == 0:
            q.append((i, j + 1, 1))
      while len(q) > 0:
         i, j, dist = q.popleft()
         if (i, j) in seen:
            continue
         seen.add((i, j))
         if mat[i][j] == 1:
            return dist - 1
         if i - 1 >= 0:
            q.append((i - 1, j, dist + 1))
         if i + 1 < row:
            q.append((i + 1, j, dist + 1))
         if j - 1 >= 0:
            q.append((i, j - 1, dist + 1))
         if j + 1 < col:
            q.append((i, j + 1, dist + 1))
ob = Solution()
matrix = [
   [0, 0, 1],
   [1, 0, 1],
   [1, 0, 0],
]
print(ob.solve(matrix))

入力

[ [0, 0, 1], [1, 0, 1], [1, 0, 0], ]

出力

1