LC 782. 变为棋盘

题目描述

这是 LeetCode 上的 782. 变为棋盘 ，难度为 困难。

一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能任意交换两列或是两行的位置。

返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换，输出 -1。

“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。

示例 1:

1
2
3
4
5
6
7
输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]

输出: 2

解释:一种可行的变换方式如下，从左到右：
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。

示例 2:

1
2
3
4
5
输入: board = [[0, 1], [1, 0]]

输出: 0

解释: 注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.

示例 3:

1
2
3
4
5
输入: board = [[1, 0], [1, 0]]

输出: -1

解释: 任意的变换都不能使这个输入变为合法的棋盘。

提示：

  • $n == board.length$
  • $n == board[i].length$
  • $2 <= n <= 30$
  • board[i][j] 将只包含 0或 1

构造分析

数据范围具有一定的迷惑性，但其并不是一个棋盘搜索问题。

我们需要考虑何种情况下无解，以及有解情况的最小步数。

在给定棋盘大小 $n$ 的前提下，所能构造的合法棋盘只有两种情况：首个格子为 $0$ 或首个格子为 $1$，即问题转化为能否构造出合法棋盘，以及构造哪种合法棋盘所用步数更小。

同时，交换行和交换列均不会影响行的种类数量和列的种类数量，因此我们可以得到第一个判断无解的条件：若起始棋盘的行/列种类数不为 $2$，必然无法构造出合法棋盘。

假设起始的行分别为 r1 和 r2，起始的列分别为 c1 和 c2。不难发现第二性质：若能构成合法棋盘，r1 和 r2 中 $0$ 和 $1$ 的数量必然相等，c1 和 c2 中的 $0$ 和 $1$ 的数量必然相等。

同时由于交换行和交换列具有对称性和独立性，我们可以先使用「交换列」来进行分析，交换列不会导致行种类发生变化，但会导致行的数值分布发生变化。

因此第二性质可拓展为：r1 和 r2 对称位置为必然不同，c1 和 c2 对称位置必然不同，即两者异或结果为必然为 $(111…111)_2$，即为 mask = (1 << n) - 1，否则必然无解。

若上述两性质满足，可能有解。

由于 r1 和 r2 及 c1 和 c2 对称位置必然不同，因此我们调整好 r1 后，r2 唯一确定（c1 和 c2 同理），同时构造其中一种间隔行为 t = $(…101)_2$，根据合法棋盘定义可知要么是将首行调整为 $t$，要么是将次行调整为 $t$。

我们设置函数 int getCnt(int a, int b) 计算将 a 变为 b 所需要的最小转换次数，两状态转换所需次数为不同位个数除以 $2$（一次交换可实现消除两个不同位）。

分别计算「将 r1 和 r2 转换为 t 所需步数」和「将 c1 和 c2 转换为 t 所需步数」，两者之和即为答案。

Java 代码：

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
class Solution {
    int n = 0, INF = 0x3f3f3f3f;
    int getCnt(int a, int b) {
        return Integer.bitCount(a) != Integer.bitCount(b) ? INF : Integer.bitCount(a ^ b) / 2;
    }
    public int movesToChessboard(int[][] g) {
        n = g.length;
        int r1 = -1, r2 = -1, c1 = -1, c2 = -1, mask = (1 << n) - 1;
        for (int i = 0; i < n; i++) {
            int a = 0, b = 0;
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) a += (1 << j);
                if (g[j][i] == 1) b += (1 << j);
            }
            if (r1 == -1) r1 = a;
            else if (r2 == -1 && a != r1) r2 = a;
            if (c1 == -1) c1 = b;
            else if (c2 == -1 && b != c1) c2 = b;
            if (a != r1 && a != r2) return -1;
            if (b != c1 && b != c2) return -1;
        }
        if (Integer.bitCount(r1) + Integer.bitCount(r2) != n) return -1;
        if (Integer.bitCount(c1) + Integer.bitCount(c2) != n) return -1;
        if ((r1 ^ r2) != mask || (c1 ^ c2) != mask) return -1;
        int t = 0;
        for (int i = 0; i < n; i += 2) t += (1 << i);
        int ans = Math.min(getCnt(r1, t), getCnt(r2, t)) + Math.min(getCnt(c1, t), getCnt(c2, t));
        return ans >= INF ? -1 : ans;
    }
}

C++ 代码：
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
class Solution {
public:
    int n = 0, INF = 0x3f3f3f3f;
    int getCnt(int a, int b) {
        return __builtin_popcount(a) != __builtin_popcount(b) ? INF : (__builtin_popcount(a ^ b) / 2);
    }
    int movesToChessboard(vector<vector<int>>& g) {
        n = g.size();
        int r1 = -1, r2 = -1, c1 = -1, c2 = -1, mask = (1 << n) - 1;
        for (int i = 0; i < n; i++) {
            int a = 0, b = 0;
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) a |= (1 << j);
                if (g[j][i] == 1) b |= (1 << j);
            }
            if (r1 == -1) r1 = a;
            else if (r2 == -1 && a != r1) r2 = a;
            if (c1 == -1) c1 = b;
            else if (c2 == -1 && b != c1) c2 = b;
            if (a != r1 && a != r2) return -1;
            if (b != c1 && b != c2) return -1;
        }
        if (__builtin_popcount(r1) + __builtin_popcount(r2) != n) return -1;
        if (__builtin_popcount(c1) + __builtin_popcount(c2) != n) return -1;
        if ((r1 ^ r2) != mask || (c1 ^ c2) != mask) return -1;
        int t = 0;
        for (int i = 0; i < n; i += 2) t |= (1 << i);
        int ans = min(getCnt(r1, t), getCnt(r2, t)) + min(getCnt(c1, t), getCnt(c2, t));
        return (ans >= INF) ? -1 : ans;
    }
};

TypeScript 代码：
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
let n: number = 0, INF = 0x3f3f3f3f
function bitCount(x: number): number {
    let ans = 0
    while (x != 0 && ++ans >= 0) x -= (x & -x)
    return ans
}
function getCnt(a: number, b: number): number {
    return bitCount(a) != bitCount(b) ? INF : bitCount(a ^ b) / 2
}
function movesToChessboard(g: number[][]): number {
    n = g.length
    let r1 = -1, r2 = -1, c1 = -1, c2 = -1, mask = (1 << n) - 1
    for (let i = 0; i < n; i++) {
        let a = 0, b = 0
        for (let j = 0; j < n; j++) {
            if (g[i][j] == 1) a += (1 << j)
            if (g[j][i] == 1) b += (1 << j)
        }
        if (r1 == -1) r1 = a
        else if (r2 == -1 && a != r1) r2 = a
        if (c1 == -1) c1 = b
        else if (c2 == -1 && b != c1) c2 = b
        if (a != r1 && a != r2) return -1
        if (b != c1 && b != c2) return -1
    }
    if (bitCount(r1) + bitCount(r2) != n) return -1
    if (bitCount(c1) + bitCount(c2) != n) return -1
    if ((r1 ^ r2) != mask || (c1 ^ c2) != mask) return -1
    let t = 0
    for (let i = 0; i < n; i += 2) t += (1 << i)
    const ans = Math.min(getCnt(r1, t), getCnt(r2, t)) + Math.min(getCnt(c1, t), getCnt(c2, t))
    return ans >= INF ? -1 : ans
};

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.782 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。