题目描述

注释版

样例

class Solution {
public:
    const int INF = 1e8;

    // 1的个数
    int get_count(int x) {
        int res = 0;
        while (x) res += x & 1, x >>= 1;
        return res;
    }

    int get(int a, int b) {
        if (get_count(a) != get_count(b)) return INF;
        // 异或得出不相同的位置 不相同值为1
        return get_count(a ^ b) / 2;
    }

    int movesToChessboard(vector<vector<int>>& board) {
        set<int> row, col;
        int n = board.size();
        // 棋盘只有两种可能 1010 0101
        for (int i = 0; i < n; i ++ ) {
            int r = 0, c = 0;
            for (int j = 0; j < n; j ++ ) {
                // 取出棋盘每一位 变成二进制
                r = r << 1 | board[i][j];
                c = c << 1 | board[j][i];
            }
            row.insert(r), col.insert(c);
        }
        // 没有2种可能 
        // 不存在可行的变换，输出 -1。
        if (row.size() != 2 || col.size() != 2) return -1;

        // begin()-返回指向第一个元素的迭代器
        // rbegin()–返回指向集合中最后一个元素的反向迭代器
        int r1 = *row.begin(), r2 = *row.rbegin();
        int c1 = *col.begin(), c2 = *col.rbegin();
        // 异或是否全1
        if ((r1 ^ r2) != (1 << n) - 1 || (c1 ^ c2) != (1 << n) - 1) return -1;
        // s1 = 0101
        int s1 = 0;
        for (int i = 0; i < n; i += 2) s1 |= 1 << i;
        // s2 = 1010
        int s2 = ((1 << n) - 1) ^ s1;
        // 行和列变成两种可能 取最小
        int r_cost = min(get(r1, s1), get(r1, s2));
        int c_cost = min(get(c1, s1), get(c1, s2));
        int res = r_cost + c_cost;
        if (res >= INF) return -1;
        return res;
    }
};