【leetcode】【2022/8/23】782. 变为棋盘

问题描述：

• 一个 n x n 的二维网络 board 仅由 0 和 1 组成。
  • 每次移动，能任意交换两列或是两行的位置。
  • 返回将这个矩阵变为棋盘所需的最小移动次数。
  • 如果不存在可行的变换，输出 -1。
  • 满足 2 <= n <= 30。
• 棋盘是指任意一格的上下左右四个方向的值均与本身不同的矩阵。
• 例子如下：
  

核心思路：

• 该题比较有意思，因为它考察的是位运算。
• 一开始通过观察可以得出结论：如果某一行或者某一列中 1 和 0 的数量差距超过 1，则原二维数组无法转变为棋盘。
  • 但单凭这一点无法判断二维数组转为棋盘的合法性，经过评论区提醒终于理解了：

    这题的思路是：因为只能行列变换，所以棋盘上所有行的种类只会有2种，而且这2种是完全相反的，也就是说只要计算一行就可以了。而列也同理，因此可以把棋盘简化为一行一列，只用在一行一列内操作就可以了。那么如果棋盘出现了不止这两对相反的排列，或者是单一行列内黑白差距大于1，就是不存在解法的情况。

  • 因此可以先遍历整个数组，确定行和列的排列种类是否只有两种，其中同时判断单行或单列中数量差距是否超过 1（只要保证数量差距不超过，且排列种类只有两种，则这两种排列组合必然完全相反）。
  • 但是如何保存行和列的排列种类？
    • 答案是通过位运算保存进一个 32 位整数中（题目限制为 2 <= n <= 30）。
    • 因此行 (0, 1, 1, 0) 会被保存为 0b0110 = 6。
• 前面已经把判断二维数组转为棋盘的合法性进行了讨论，后续就是要进行移动来实现棋盘。

  • 关键在于理解棋盘：棋盘中每一行（或每一列）都是 0 和 1 相间的。

  • 从具体例子中可以更好理解，假设某个行为 (0, 1, 1)，则和它完全相反的另一行为 (1, 0, 0)：【这里只讨论行，列的操作是一样的】
    

  • 可以看出两个转变所需要的移动次数是一样的，这也就是前面评论里说的“只用在一行一列内操作就可以了”。

  • 到这里其实获得移动次数的方法已经呼之欲出：那就是异或！【复习一下，异或是对应位不相同就置 1】

  • 再次从前面的例子中可以看出 0b011 与 0b101 进行异或，异或结果是 0b110，异或结果表明原来的两行存在 diff = 2 位不同，则只需要通过 diff/2 = 2/2 = 1 次移动就可变为棋盘。

  • 但是前面讨论的前提是，我们知道 0b011 最后会转变为 0b101，然而要提前知道转变结果也比较麻烦，需要统计原数值二进制表达中 1 和 0 的个数，更好的办法是直接构造两种可能性，即 0b101 和 0b010，将原排列 0b011 与前面两种排列结果进行异或操作，如果异或结果中不同的位数 diff 为奇数，则可以抛弃该结果，具体如图所示：
    

  • 还存在另一种情况，如果 n 为偶数，则两个异或结果中 diff 均为偶数，此时取更小值即可得出移动结果，具体如图所示：
    

代码实现：

class Solution
{
public:
    int movesToChessboard(vector<vector<int>>& board)
    {
        // 验证合法性
        unordered_set<int> row;
        unordered_set<int> col;
        int m = board.size();
        int r, c;
        for(int i = 0; i < m; ++i)
        {
            r = 0, c = 0;
            int r0 = 0, r1 = 0;
            int c0 = 0, c1 = 0;
            for(int j = 0; j < m; ++j)
            {
                r <<= 1;
                c <<= 1;
                r += board[i][j];
                c += board[j][i];
                r0 += board[i][j] == 0;
                r1 += board[i][j] == 1;
                c0 += board[j][i] == 0;
                c1 += board[j][i] == 1;
            }
            if((abs(r0 - r1) > 1) or (abs(c0 - c1) > 1)) return -1;
            row.insert(r);
            col.insert(c);
            if(row.size() > 2 or col.size() > 2)
                return -1;
        }
        // 获得移动次数
        r = *row.begin();
        c = *col.begin();
        int a = 0, b = 0; // 构造最后排列结果
        for(int i = 0; i < m; ++i)
        {
            a <<= 1, b <<= 1;
            a += (i & 1), b += ((i+1) & 1);
        }
        int ar = a ^ r; ar = (bitset<32> (ar)).count(); // 进行异或判断二进制表达中不同的位数
        int br = b ^ r; br = (bitset<32> (br)).count();
        int ac = a ^ c; ac = (bitset<32> (ac)).count();
        int bc = b ^ c; bc = (bitset<32> (bc)).count();
        int ans = (ar & 1) == 1 ? br/2 : (br & 1) == 1 ? ar/2 : min(ar,br)/2;
        ans += (ac & 1) == 1 ? bc/2 : (bc & 1) == 1 ? ac/2 : min(ac, bc)/2;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50