使用Python查找排列二进制网格所需的最小交换次数

假设我们有一个n x n的二进制矩阵。我们可以对它执行像这样的操作，在一步中，我们选择两个相邻的行并交换它们。我们必须计算所需的最小交换次数，以便矩阵主对角线上方的所有节点都为0。如果没有这样的解决方案，则返回-1。

因此，如果输入如下所示

0	1	0
0	1	1
1	0	0

则输出将为2，因为−

为了解决这个问题，我们将遵循以下步骤：

n：=矩阵的行数
m：=制作大小为n的数组，并填充n
对于i在范围0到n-1内，执行以下操作：
- 对于j在n-1到0范围内，递减1，执行以下操作：
  - 如果matrix [i，j]与1相同，则
  - m [i]：= n-j-1
  - 退出循环
t：=0，ans：=0
对于i在范围0到n-1内，执行以下操作：
- t：= t + 1
- flag：= False
- 对于j在范围i到n-1内，执行以下操作：
  - 如果m [j]≥n-t，则
  - ans：= ans + j-i
  - flag：= True
  - 退出循环
- 如果标志为false，则
  - 返回-1
- 通过m [从索引i + 1到j]更新m [从索引i到j-1]
返回ans

让我们看看以下实现以更好地理解 −

更多Python相关文章，请阅读：Python 教程

示例

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))