Minimum Swaps to Arrange a Binary Grid
Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.
A grid is said to be valid if all the cells above the main diagonal are zeros.
Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.
The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).
Example 1
0 0 1 1 1 0 1 0 0
Input
grid = [[0,0,1],[1,1,0],[1,0,0]]Output
3After three adjacent row swaps, the grid can be rearranged so every cell above the main diagonal is 0.
Example 2
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
Input
grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]Output
-1All rows are similar, swaps have no effect on the grid.
Constraints
- n == grid.length == grid[i].length
- 1 <= n <= 200
- grid[i][j] is either 0 or 1