# leetcode 1536. Minimum Swaps to Arrange a Binary Grid 贪心冒泡排序

#### 题目

https://leetcode.com/contest/weekly-contest-200/problems/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:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3
Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.
Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] is 0 or 1

#### 源码

``````class Solution {
public:
int minSwaps(vector<vector<int>>& grid) {
vector<int> nums;
for(auto p:grid){
int count = 0;
for(int i = p.size()-1;i>=0;--i){
if(p[i]==0){
count++;
}else break;
}
nums.push_back(count);
}
int res = 0;
for(int i = 0;i < nums.size();++i){
if(nums[i] < nums.size()-i-1){
bool f = true;
for(int j = i+1;j < nums.size();++j){
if(nums[j]>=nums.size()-i-1){
int t = nums[j];
nums.erase(nums.begin()+j);
nums.insert(nums.begin()+i,t);
res += j-i;
f = false;
break;
}
}
if(f)return -1;
}
}
return res;
}
};
``````