1536. Minimum Swaps to Arrange a Binary Grid

题目信息

题号:

1536

难度:

Medium

主题:

二进制矩阵、贪心、相邻交换

原题:

LeetCode 1536

重点:

只能交换相邻两行;目标要求主对角线上方全部为零,即第 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
解释:首行需要至少两个尾零,但所有行最多只有一个。