782. Transform to Chessboard

Problem

You are given an n x n binary grid board. In each move, you can swap any two rows with each other, or any two columns with each other.

Return the minimum number of moves to transform the board into a chessboard board. If the task is impossible, return -1.

A chessboard board is a board where no 0’s and no 1’s are 4-directionally adjacent.

https://leetcode.cn/problems/transform-to-chessboard/

Example 1:

Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation: One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.

Example 2:

case2

Input: board = [[0,1],[1,0]]
Output: 0
Explanation: Also note that the board with 0 in the top left corner, is also a valid chessboard.

Example 3:

case3

Input: board = [[1,0],[1,0]]
Output: -1
Explanation: No matter what sequence of moves you make, you cannot end with a valid chessboard.

Constraints:

n == board.length
n == board[i].length
2 <= n <= 30
board[i][j] is either 0 or 1.

Test Cases

1 2	class Solution: def movesToChessboard(self, board: List[List[int]]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('board, expected', [
    ([[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]], 2),
    ([[0,1],[1,0]], 0),
    ([[1,0],[1,0]], -1),

    ([[1,0],[0,1]], 0),
    ([[1,1,0],[0,0,1],[0,0,1]], 2),
])
class Test:
    def test_solution(self, board, expected):
        sol = Solution()
        assert sol.movesToChessboard(board) == expected

Thoughts

先看第一行。其中 0 的个数和 1 个数必须相等（对于偶数 n）或者刚好相差 1（对于奇数 n），否则就无法变为棋盘。

第一列也是一样的。

然后看后续的每一行，只能有两个可能，要么跟第一行完全一致，要么跟第一行完全互补（0 和 1 互补）。否则也无法变为棋盘。

按照此条件检查完所有行如果成功，所有列也就自动符合相同要求，不用额外检查。

以上条件都符合的话，board 一定可以变为棋盘，否则不行。

再看第一行，看其中不在正确位置的 0 和 1 有多少个，该个数除以 2 就是复原所需要的列交换次数。有个问题是正确的位置应该是什么。

当 n 是奇数时，如果这行中 1 的个数多，则正确的排列是 1 - 0 - 1 - ... - 0 - 1，否则是 0 - 1 - 0 - ... - 1 - 0。

当 n 是偶数时，正确的排列是 0 - 1 - 0 - ... - 0 - 1 或者 1 - 0 - 1 - ... - 1 - 0。两种情况对应的排列错误数量（相加等于 n）取较小的即可。

再用同样方法计算第一列中不在正确位置的 0 和 1 的个数，除以 2 是需要的行交换次数。

最终总共所需的交换次数为 列交换次数 + 行交换次数。

Code

solution.py

class Solution:
    def movesToChessboard(self, board: list[list[int]]) -> int:
        n = len(board)
        cnt = 0

        # Check first row / column.
        for b in (lambda c: board[0][c], lambda r: board[r][0]):
            one = zero = 0 # The number of `1` and `0`s.
            wrong = 0 # The number of mis-placed `1` or `0`s.
            for j in range(n):
                v = b(j)
                one += v
                zero += 1 - v
                wrong += v ^ (j & 1)

            if not -1 <= one - zero <= 1:
                return -1

            if one > zero or one == zero and n - wrong < wrong:
                wrong = n - wrong

            cnt += wrong >> 1

        # Check whether other rows same with or complementary to the first row.
        for i in range(1, n):
            first = board[i][0] ^ board[0][0]
            for j in range(1, n):
                if board[i][j] ^ board[0][j] != first:
                    return -1

        return cnt

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。