LWC 71: 782. Transform to Chessboard
LWC 71: 782. Transform to Chessboard
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434585
LWC 71: 782. Transform to Chessboard
传送门：782. Transform to Chessboard
Problem:
An N x N board contains only 0s and 1s. 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 0s and no 1s 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.
- boardi will be only 0s or 1s.
思路：
刚开始采用暴力BFS搜索最小step，超时。得关注一波此题的性质，首先最终状态必须是01交叉，所以如果某一行0的个数和1的个数之差大于1，那么可以直接返回-1了。预处理代码如下：
boolean check(int[][] board) {
int N = board.length;
// check row
for (int i = 0; i < N; ++i) {
int num_1 = 0;
int num_0 = 0;
for (int j = 0; j < N; ++j) {
if (board[i][j] == 0)
num_0++;
else
num_1++;
}
if (Math.abs(num_1 - num_0) > 1)
return false;
}
// check col
for (int i = 0; i < N; ++i) {
int num_1 = 0;
int num_0 = 0;
for (int j = 0; j < N; ++j) {
if (board[j][i] == 0)
num_0++;
else
num_1++;
}
if (Math.abs(num_1 - num_0) > 1)
return false;
}
return true;
}现在考虑换行的性质，实际上不管你换哪两行或者哪两列，最小步数只要看首列和首行即可。举个例子：
N = 4
0 ? ? ?
1 ? ? ?
1 ? ? ?
0 ? ? ?
看第一列，我们怎么交换呢？可以交换最后两行得到：
0 ? ? ?
1 ? ? ?
0 ? ? ?
1 ? ? ?
交换一次即可。注意：因为1和1之间必须要被相互隔开，所以后续的?我们不用去关注。因为如果：
0 ? ? ?
1 ? 1 ?
0 ? ? ?
1 ? 0 ?
出现第三列相异的情况时，不管我们后续交换哪两行，都无法满足01交叉的性质。（反证法）
比如第三列第四行出现了0，但根据01交叉性质来说，0只能在偶数行，可一旦把0换到偶数行，第一列的01交叉性质又被破坏了，显然矛盾。
换个角度来考虑，当首行和首列都满足01交叉性质时：
0 1 0 1
1 ? ? ?
0 ? ? ?
1 ? ? ?
这些“?”就已经被唯一确定了，所以只要计算交换首行和首列的次数即可。如果“?”中没有满足01交叉性质，在check时就能被发现了。代码如下：
public int getResult(int[] line) {
int N = line.length;
int value1 = 0 , value2 = 0 , ans = - 1;
int cnt1 = 0 , cnt2 = 0;
for (int i = 0;i < N; ++i) {
int need = (i % 2 == 0) ? 1 : 0;
if (line[i] != need) {
value1 ++;
}
if (line[i] == 0) {
cnt1 ++;
}
if (need == 0) {
cnt2 ++;
}
}
if (cnt1 == cnt2) {
value1 /= 2;
if (value1 < ans || ans < 0) {
ans = value1;
}
}
cnt1 = cnt2 = 0;
for (int i = 0;i < N;i ++) {
int need = (i % 2 == 0) ? 0 : 1;
if (line[i] != need) {
value2 ++;
}
if (line[i] == 0) {
cnt1 ++;
}
if (need == 0) {
cnt2 ++;
}
}
if (cnt1 == cnt2) {
value2 /= 2;
if (value2 < ans || ans < 0) {
ans = value2;
}
}
return ans;
}
boolean check(int[][] board) {
int N = board.length;
// check row
for (int i = 0; i < N; ++i) {
int num_1 = 0;
int num_0 = 0;
for (int j = 0; j < N; ++j) {
if (board[i][j] == 0)
num_0++;
else
num_1++;
}
if (Math.abs(num_1 - num_0) > 1)
return false;
}
// check col
for (int i = 0; i < N; ++i) {
int num_1 = 0;
int num_0 = 0;
for (int j = 0; j < N; ++j) {
if (board[j][i] == 0)
num_0++;
else
num_1++;
}
if (Math.abs(num_1 - num_0) > 1)
return false;
}
return true;
}
public int movesToChessboard(int[][] board) {
if (check(board)) {
int n = board.length;
int[] col = new int[n];
for (int i = 0; i < n; ++i) col[i] = board[i][0];
return getResult(board[0]) + getResult(col);
}
return -1;
}