Pythonを使用してバイナリグリッドを配置するための最小スワップを見つけるプログラム

nxnのバイナリ行列があるとします。 1つのステップで、隣接する2つの行を選択し、それらを入れ替えるような操作を実行できます。行列の主対角線より上のすべてのノードが0になるように、必要な最小スワップの数をカウントする必要があります。そのような解決策がない場合は、-1を返します。

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

-

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

• n：=行列の行数

• m：=サイズnの配列を作成し、nで埋めます

• 0からn-1の範囲のiの場合、実行

  • n-1から0の範囲のjの場合、1ずつ減らします。

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

      • m [i]：=n-j-1

      • ループから出てきます

• t：=0、ans：=0

• 0からn-1の範囲のiの場合、実行

  • t：=t + 1

  • フラグ：=False

  • iからn-1の範囲のjの場合、実行

    • m [j]> =n-tの場合、

      • ans：=ans + j-i

      • フラグ：=True

      • ループから出てきます

  • フラグがfalseの場合、

    • -1を返す

  • m[インデックスi+1からjへ]をm[インデックスiからj-1へ]で更新

• ansを返す

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

例

def solve(matrix):
   n = len(matrix)
   m = [n] * n
   for i in range(n):
      for j in range(n-1,-1,-1):
         if matrix[i][j] == 1:
            m[i] = n-j-1
            break
   t,ans = 0,0
   for i in range(n):
      t += 1
      flag = False
      for j in range(i,n):
         if m[j] >= n-t:
            ans += j-i
            flag = True
            break
      if not flag: return -1
      m[i+1:j+1] = m[i:j]
   return ans
matrix = [[0,1,0],[0,1,1],[1,0,0]]
print(solve(matrix))

入力

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

出力

2