Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 1536. Minimum Swaps to Arrange a Binary Grid

---

參考資訊：
https://algo.monster/liteproblems/1536

題目：


方法：
1. 找出每一列最右邊的"1"
2. 第一列(紅色)的第一行可以"1"或"0"，但是第二行後面都必須是"0"
3. 第二列(綠色)的第一、二行可以"1"或"0"，但是第三行後面都必須是"0"
4. 第三列(藍色)的第一、二、三行可以"1"或"0"
5. 使用vector儲存每一列最右邊是"1"的位置
6. 依據vector從小的位置交換排序到大的位置即可


解答：

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int size = grid.size();
        vector<int> q(size, -1);

        for (int i = 0; i < size; ++i) {
            for (int j = size - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    q[i] = j;
                    break;
                }
            }
        }

        int r = 0;
        for (int i = 0; i < size; ++i) {
            int found = -1;

            for (int j = i; j < size; ++j) {
                if (q[j] <= i) {
                    found = j;
                    break;
                }
            }

            if (found == -1) {
                return -1;
            }

            for (int k = found; k > i; --k) {
                r += 1;
                swap(q[k], q[k - 1]);
            }
        }

        return r;
    }
};