1536. Minimum Swaps to Arrange a Binary Grid¶
题目信息¶
- 题号:
1536
- 难度:
Medium
- 主题:
二进制矩阵、贪心、相邻交换
- 原题:
- 重点:
只能交换相邻两行;目标要求主对角线上方全部为零,即第
i行末尾至少有n-1-i个零
题目重述¶
给定 n x n 二进制矩阵 grid。一次操作可以交换任意两行相邻的行。
请用最少操作使所有满足 j > i 的格子 grid[i][j] 都为 0。若无法做到,返回 -1。
1 <= n <= 200,每个元素为 0 或 1。
自建示例¶
需要把拥有足够尾零的行逐步上移:
输入:grid = [[0,0,1],[1,1,0],[1,0,0]]
输出:3
解释:各行尾零数为 0、1、2;先把第三行移到顶部需要两次,再把原第二行移到中间需要一次。
没有任何行满足首行尾零要求时无解:
输入:grid = [[1,1,1],[1,1,1],[1,1,0]]
输出:-1
解释:首行需要至少两个尾零,但所有行最多只有一个。