题目描述

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

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

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

示例

示例 1:

img

1
2
3
4
5
输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:一种可行的变换方式如下，从左到右：
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。

示例 2:

img

1
2
3
输入: board = [[0, 1], [1, 0]]
输出: 0
解释: 注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.

示例 3:

img

1
2
3
输入: board = [[1, 0], [1, 0]]
输出: -1
解释: 任意的变换都不能使这个输入变为合法的棋盘。

提示：

1
2
3
4
n == board.length
n == board[i].length
2 <= n <= 30
board[i][j] 将只包含 `0`或 `1`

代码

只有 c++ 版本有详细注释，其它都是仿照 c++ 版本写的！

分维度计算 (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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
 * @lc app=leetcode.cn id=782 lang=cpp
 *
 * [782] 变为棋盘
 */

// @lc code=start
class Solution {
public:
    
    int getOneCnt(int mask, int n) {
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res += mask & 0x01;
            mask >>= 1;
        }
        return res;
    }
    
    /** 
     * get move count.
     * @mask: row_mask or col_mask.
     * @cnt: row_cnt or col_cnt.
     * @n: board length.
     */
    int getMoveCnt(int mask, int cnt, int n) {
        
        int mask_one_cnt = getOneCnt(mask, n);
        // return cnt;
        // return mask_one_cnt;

        /** 
         * 分 n 值为奇数偶数两种情况
         */
        if (!(n % 2)) {
            if ((n / 2) != mask_one_cnt || (n / 2) != cnt) {
                return -1;
            }
            int cnt0 = n / 2 - getOneCnt(mask & 0xaaaaaaaa, 32);
            int cnt1 = n / 2 - getOneCnt(mask & 0x55555555, 32);
            return cnt0 < cnt1 ? cnt0 : cnt1;
        } else {
            int ym = n - mask_one_cnt * 2, yc = n - cnt * 2;
            ym = ym < 0 ? -ym : ym;
            yc = yc < 0 ? -yc : yc;
            if (ym != 1 || yc != 1) {
                return -1;
            }
            if (mask_one_cnt == n / 2) {
                return n / 2 - getOneCnt(mask & 0xaaaaaaaa, 32);
            } else {
                return (n + 1) / 2 - getOneCnt(mask & 0x55555555, 32);
            }
        }
    }

    int movesToChessboard(vector<vector<int>>& board) {
        
        int row_mask = 0, col_mask = 0;
        
        /* 棋盘的长和宽 */
        int n = board.size();
        
        /** 
         * 得到第 1 行和第 1 列的值
         */
        for (int i = 0; i < n; ++i) {
            row_mask |= (board[0][i] << i);
            col_mask |= (board[i][0] << i);
        }
        // return getOneCnt(col_mask, 32);
        int reverse_row_mask = ((1 << n) - 1) ^ row_mask;
        int reverse_col_mask = ((1 << n) - 1) ^ col_mask;
        int row_cnt = 0, col_cnt = 0;
        for (int i = 0; i < n; ++i) {
            int curr_row_mask = 0;
            int curr_col_mask = 0;

            /** 
             * 第 i 行 或 第 i 列分别与第 1 行或第一列比较 
             */
            for (int j = 0; j < n; ++j) {
                curr_row_mask |= (board[i][j] << j);
                curr_col_mask |= (board[j][i] << j);
            }
            if (curr_col_mask != col_mask && curr_col_mask != reverse_col_mask) {
                return -1;
            } else if (curr_col_mask == col_mask) {
                ++col_cnt;
            }
            if (curr_row_mask != row_mask && curr_row_mask != reverse_row_mask) {
                return -1;
            } else if (curr_row_mask == row_mask) {
                ++row_cnt;
            }

        }
        int row_moves = getMoveCnt(row_mask, row_cnt, n);
        int col_moves = getMoveCnt(col_mask, col_cnt, n);
        // return row_moves;
        // return col_moves;
        return (row_moves == -1 || col_moves == -1) ? -1 : row_moves + col_moves;
    }
};
// @lc code=end

分维度计算(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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*
 * @lc app=leetcode.cn id=782 lang=java
 *
 * [782] 变为棋盘
 */

// @lc code=start
class Solution {

    public int getOneCnt(int num) {
        int res = 0;
        while  (num > 0) {
            res += num & 0x01;
            num >>= 1;
        }
        return res;
    }

    public int getMoveCnt(int board_length, int mask, int cnt) {
        int mask_one_cnt = getOneCnt(mask);
        // return 7;
        // return mask_one_cnt;
        
        if (board_length % 2 == 0) {
            if ((board_length / 2) != mask_one_cnt || (board_length / 2) != cnt) {
                return -1;
            }
            // int cnt0 = (board_length / 2) - getOneCnt(mask & 0xaaaaaaaa);
            // int cnt1 = (board_length / 2) - getOneCnt(mask & 0x55555555);
            int cnt0 = getOneCnt(mask & 0xaaaaaaaa);
            int cnt1 = getOneCnt(mask & 0x55555555);
            return cnt0 < cnt1 ? cnt0 : cnt1;
        } else {
            int ym = board_length - mask_one_cnt * 2, yc = board_length - cnt * 2;
            ym = ym < 0 ? -ym : ym;
            yc = yc < 0 ? -yc : yc;
            if (ym != 1 || yc != 1) return -1;
            if (mask_one_cnt == board_length / 2) {
                // return board_length / 2 - getOneCnt(mask & 0xaaaaaaaa);
                return mask_one_cnt - getOneCnt(mask & 0xaaaaaaaa);
            } else {
                // return (board_length + 1) / 2 - getOneCnt(mask & 0x55555555);
                return mask_one_cnt - getOneCnt(mask & 0x55555555);
            }
        }
    }

    public int movesToChessboard(int[][] board) {
        int row_mask = 0, col_mask = 0;
        int n = board.length;

        for (int i = n - 1; i > -1; --i) {
            row_mask |= (board[0][i] << i);
            col_mask |= (board[i][0] << i);
        }

        int reverse_row_mask = ((1 << n) - 1) ^ row_mask;
        int reverse_col_mask = ((1 << n) - 1) ^ col_mask;
        int row_cnt = 0, col_cnt = 0;
        // return reverse_row_mask;

        for (int i = 0; i < n; ++i) {
            int curr_row_mask = 0;
            int curr_col_mask = 0;
        
            for (int j = n - 1; j > -1; --j) {
                curr_col_mask |= (board[j][i] << j);
                curr_row_mask |= (board[i][j] << j);
            }

            if (reverse_col_mask != curr_col_mask && col_mask != curr_col_mask) {
                return -1;
            }
            if (reverse_row_mask != curr_row_mask && row_mask != curr_row_mask) {
                return -1;
            }
            if (col_mask == curr_col_mask) {
                ++col_cnt;
            }
            if (row_mask == curr_row_mask) {
                ++row_cnt;
            }
        }

        int col_move_cnt = getMoveCnt(n, col_mask, col_cnt);
        int row_move_cnt = getMoveCnt(n, row_mask, row_cnt);

        // return col_move_cnt;
        return col_move_cnt == -1 || row_move_cnt == -1 ? -1 : col_move_cnt + row_move_cnt;
    }
}
// @lc code=end

分维度计算(python3)

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#
# @lc app=leetcode.cn id=782 lang=python3
#
# [782] 变为棋盘
#

# @lc code=start
class Solution:

    def movesToChessboard(self, board: List[List[int]]) -> int:
        col_mask, row_mask = 0, 0
        n = len(board) 
        for i in range(n):
            row_mask |= (board[0][i] << i)
            col_mask |= (board[i][0] << i)
        reserve_row_mask = (1 << n) - 1 ^ row_mask
        reserve_col_mask = (1 << n) - 1 ^ col_mask
        row_cnt = col_cnt = 0
        
        for i in range(n):
            curr_row_mask = curr_col_mask = 0
            for j in range(n):
                curr_row_mask |= (board[i][j] << j)
                curr_col_mask |= (board[j][i] << j)
            if curr_row_mask != row_mask and curr_row_mask != reserve_row_mask:
                return -1
            if curr_col_mask != col_mask and curr_col_mask != reserve_col_mask:
                return -1
            if row_mask == curr_row_mask:
                row_cnt += 1
            if col_mask == curr_col_mask:
                col_cnt += 1
            
        def getOneCnt(num: int) -> int:
            res = 0
            while num > 0:
                res += num & 0x01
                num >>= 1
            return res

        def getMoveCnt(board_size: int, mask: int, cnt: int) -> int:
            mask_one_cnt = getOneCnt(mask)
            if board_size % 2 == 0:
                if mask_one_cnt != board_size // 2 or cnt != board_size // 2:
                    return -1
                cnt0 = mask_one_cnt - getOneCnt(mask & 0xaaaaaaaa)
                cnt1 = mask_one_cnt - getOneCnt(mask & 0x55555555)
                return min(cnt0, cnt1)
            else:
                ym = board_size - mask_one_cnt * 2
                yc = board_size - cnt * 2
                if ym < 0:
                    ym = -ym
                if yc < 0:
                    yc = -yc
                if ym != 1 or yc != 1:
                    return -1
                if board_size // 2 == mask_one_cnt:
                    return mask_one_cnt - getOneCnt(mask & 0xaaaaaaaa)
                else:
                    return mask_one_cnt - getOneCnt(mask & 0x55555555)

        row_move_cnt = getMoveCnt(n, row_mask, row_cnt)
        col_move_cnt = getMoveCnt(n, col_mask, col_cnt)

        return -1 if row_move_cnt == -1 or col_move_cnt == -1 else row_move_cnt + col_move_cnt

# @lc code=end