# 782. Transform to Chessboard

An N x N `board` contains only `0`s and `1`s. In each move, you can swap any 2 rows with each other, or any 2 columns with each other.

What is the minimum number of moves to transform the board into a “chessboard” - a board where no `0`s and no `1`s are 4-directionally adjacent? If the task is impossible, return -1.

``````Examples:
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 below, from left to right:

0110     1010     1010
0110 --> 1010 --> 0101
1001     0101     1010
1001     0101     0101

The first move swaps the first and second column.
The second move swaps the second and third row.

Input: board = [[0, 1], [1, 0]]
Output: 0
Explanation:
Also note that the board with 0 in the top left corner,
01
10

is also a valid chessboard.

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

Note:

• `board` will have the same number of rows and columns, a number in the range `[2, 30]`.
• `board[i][j]` will be only `0`s or `1`s.

1 0 1 0

0 1 0 1

1 0 1 0

0 1 0 1

0 1 0 1

1 0 1 0

0 1 0 1

1 0 1 0

1 0 1

0 1 0

1 0 1

0 1 0

1 0 1

0 1 0

``````class Solution {
public:
int movesToChessboard(vector<vector<int>>& board) {
int n = board.size(), rowSum = 0, colSum = 0, rowDiff = 0, colDiff = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) return -1;
}
}
for (int i = 0; i < n; ++i) {
rowSum += board[0][i];
colSum += board[i][0];
rowDiff += (board[i][0] == i % 2);
colDiff += (board[0][i] == i % 2);
}
if (n / 2 > rowSum || rowSum > (n + 1) / 2) return -1;
if (n / 2 > colSum || colSum > (n + 1) / 2) return -1;
if (n % 2) {
if (rowDiff % 2) rowDiff = n - rowDiff;
if (colDiff % 2) colDiff = n - colDiff;
} else {
rowDiff = min(n - rowDiff, rowDiff);
colDiff = min(n - colDiff, colDiff);
}
return (rowDiff + colDiff) / 2;
}
};
``````

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

https://leetcode.com/problems/transform-to-chessboard/discuss/132113/Java-Clear-Code-with-Detailed-Explanations

https://leetcode.com/problems/transform-to-chessboard/discuss/114847/Easy-and-Concise-Solution-with-Explanation-C%2B%2BJavaPython

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation