https://leetcode.com/problems/transform-to-chessboard/
An observation is that, in a valid ChessBoard, any rectangle inside the board with corner NW, NE, SW, SE (NW here means north-west) must satisfy the validness property: (NW xor NE) == (SW xor SE),
Since the swap process does not break this property, for a given board to be valid, this property must hold. A corollary is that given a row, any other row must be identical to it or be its inverse(逆). For example if there is a row 01010011 in the board, any other row must be either 01010011 or 10101100.
With this observation, we only need to consider the first column when we're swapping rows to match the ChessBoard condition. That is, it suffies(就足够了) to find the minimum row swap to make the first column be 010101...^T or 101010...^T. (here ^T means transpose(转置).)
Similarly, it suffies to consider the first row when swapping columns.
Now the problem becomes solvable, with the following steps:
Check if the given board satisfy the validness property defined above.
Find minimum row swap to make the first column valid. If not possible, return -1.
Find minimum column swap to make the first row valid. If not possible, return -1.
Return the sum of step 2 and 3.
这道题 solutions：https://leetcode.com/problems/transform-to-chessboard/solution/
Approach #1: Dimension Independence [Accepted]
Intuition
After a swap of columns, two rows that were the same stay the same, and two rows that were different stay different. Since the final state of a chessboard has only two different kinds of rows, there must have originally been only two different kinds of rows.
Furthermore, these rows must have had half zeros and half ones, (except when the length is odd, where there could be an extra zero or one), and one row must be the opposite (0 changed to 1 and vice versa) of the other row. This is because moves do not change these properties either.
Similarly, the above is true for columns.
Now, because a row move followed by a column move is the same as a column move followed by a row move, we can assume all the row moves happen first, then all the column moves. (Note: it is not true that a row move followed by another row move is the same as those moves backwards.)
Since there are only two kinds of rows, we want the minimum number of moves to make them alternating; and similarly for columns. This reduces to a one dimensional problem, where we have an array like [0, 1, 1, 1, 0, 0] and we want to know the least cost to make it [0, 1, 0, 1, 0, 1] or [1, 0, 1, 0, 1, 0].
Algorithm
For each set of rows (and columns respectively), make sure there are only 2 kinds of lines in the right quantities that are opposites of each other.
Then, for each possible ideal transformation of that line, find the minimum number of swaps to convert that line to it's ideal and add it to the answer. For example, [0, 1, 1, 1, 0, 0] has two ideals [0, 1, 0, 1, 0, 1] or [1, 0, 1, 0, 1, 0]; but [0, 1, 1, 1, 0] only has one ideal [1, 0, 1, 0, 1].
In Java, we use integers to represent the rows as binary numbers. We check the number of differences with [1, 0, 1, 0, 1, 0, ...] by xoring with 0b010101010101.....01 = 0x55555555. To make sure we don't add extra large powers of 2, we also bitwise-AND by 0b00...0011...11 where there are N ones in this mask.
Time Complexity: O(N^2), where NN is the number of rows (and columns) in board.
Space Complexity: O(N)O(N), the space used by count.
https://leetcode.com/problems/transform-to-chessboard/discuss/132113/Java-Clear-Code-with-Detailed-Explanations
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:
boardwill have the same number of rows and columns, a number in the range[2, 30].board[i][j]will be only0s or1s
An observation is that, in a valid ChessBoard, any rectangle inside the board with corner NW, NE, SW, SE (NW here means north-west) must satisfy the validness property: (NW xor NE) == (SW xor SE),
Since the swap process does not break this property, for a given board to be valid, this property must hold. A corollary is that given a row, any other row must be identical to it or be its inverse(逆). For example if there is a row 01010011 in the board, any other row must be either 01010011 or 10101100.
With this observation, we only need to consider the first column when we're swapping rows to match the ChessBoard condition. That is, it suffies(就足够了) to find the minimum row swap to make the first column be 010101...^T or 101010...^T. (here ^T means transpose(转置).)
Similarly, it suffies to consider the first row when swapping columns.
Now the problem becomes solvable, with the following steps:
Check if the given board satisfy the validness property defined above.
Find minimum row swap to make the first column valid. If not possible, return -1.
Find minimum column swap to make the first row valid. If not possible, return -1.
Return the sum of step 2 and 3.
这道题 solutions：https://leetcode.com/problems/transform-to-chessboard/solution/
Approach #1: Dimension Independence [Accepted]
Intuition
After a swap of columns, two rows that were the same stay the same, and two rows that were different stay different. Since the final state of a chessboard has only two different kinds of rows, there must have originally been only two different kinds of rows.
Furthermore, these rows must have had half zeros and half ones, (except when the length is odd, where there could be an extra zero or one), and one row must be the opposite (0 changed to 1 and vice versa) of the other row. This is because moves do not change these properties either.
Similarly, the above is true for columns.
Now, because a row move followed by a column move is the same as a column move followed by a row move, we can assume all the row moves happen first, then all the column moves. (Note: it is not true that a row move followed by another row move is the same as those moves backwards.)
Since there are only two kinds of rows, we want the minimum number of moves to make them alternating; and similarly for columns. This reduces to a one dimensional problem, where we have an array like [0, 1, 1, 1, 0, 0] and we want to know the least cost to make it [0, 1, 0, 1, 0, 1] or [1, 0, 1, 0, 1, 0].
Algorithm
For each set of rows (and columns respectively), make sure there are only 2 kinds of lines in the right quantities that are opposites of each other.
Then, for each possible ideal transformation of that line, find the minimum number of swaps to convert that line to it's ideal and add it to the answer. For example, [0, 1, 1, 1, 0, 0] has two ideals [0, 1, 0, 1, 0, 1] or [1, 0, 1, 0, 1, 0]; but [0, 1, 1, 1, 0] only has one ideal [1, 0, 1, 0, 1].
In Java, we use integers to represent the rows as binary numbers. We check the number of differences with [1, 0, 1, 0, 1, 0, ...] by xoring with 0b010101010101.....01 = 0x55555555. To make sure we don't add extra large powers of 2, we also bitwise-AND by 0b00...0011...11 where there are N ones in this mask.
Time Complexity: O(N^2), where NN is the number of rows (and columns) in board.
Space Complexity: O(N)O(N), the space used by count.
public int movesToChessboard(int[][] board) {
int N = board.length;
// count[code] = v, where code is an integer
// that represents the row in binary, and v
// is the number of occurrences of that row
Map<Integer, Integer> count = new HashMap();
for (int[] row : board) {
int code = 0;
for (int x : row)
code = 2 * code + x;
count.put(code, count.getOrDefault(code, 0) + 1);
}
int k1 = analyzeCount(count, N);
if (k1 == -1)
return -1;
// count[code], as before except with columns
count = new HashMap();
for (int c = 0; c < N; ++c) {
int code = 0;
for (int r = 0; r < N; ++r)
code = 2 * code + board[r][c];
count.put(code, count.getOrDefault(code, 0) + 1);
}
int k2 = analyzeCount(count, N);
return k2 >= 0 ? k1 + k2 : -1;
}
public int analyzeCount(Map<Integer, Integer> count, int N) {
// Return -1 if count is invalid
// Otherwise, return number of swaps required
if (count.size() != 2)
return -1;
List<Integer> keys = new ArrayList(count.keySet());
int k1 = keys.get(0), k2 = keys.get(1);
// If lines aren't in the right quantity
if (!(count.get(k1) == N / 2 && count.get(k2) == (N + 1) / 2)
&& !(count.get(k2) == N / 2 && count.get(k1) == (N + 1) / 2))
return -1;
// If lines aren't opposite
if ((k1 ^ k2) != (1 << N) - 1)
return -1;
int Nones = (1 << N) - 1;
int ones = Integer.bitCount(k1 & Nones);
int cand = Integer.MAX_VALUE;
if (N % 2 == 0 || ones * 2 < N) // zero start
cand = Math.min(cand, Integer.bitCount(k1 ^ 0xAAAAAAAA & Nones) / 2);
if (N % 2 == 0 || ones * 2 > N) // ones start
cand = Math.min(cand, Integer.bitCount(k1 ^ 0x55555555 & Nones) / 2);
return cand;
}
https://www.cnblogs.com/grandyang/p/9053705.html
这道题给了我们一个二维数组，里面都是由0和1组成的，让我们通过交换行或者列来形成一个棋盘。棋盘我们都见过吧，就是国际象棋的那种棋盘，黑白相间的那种，用数组表示就是0和1交替出现，相邻位置上的数字必定不是一样的。这道题默认的棋盘的起始位置可以是1或者0，然后依次类推可得到所有位置上的值。这道题最大的难点是在于判断给定的数组最终能否组成棋盘，因为能通过交换组成棋盘的数组其实是有很多苛刻条件需要满足的，只有这些条件都满足了，才能到计算交换数到那一步。首先我们先来看长度为4的棋盘：
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
我们发现对于长度为偶数的棋盘，每一行0和1的个数都是相等的，不管我们如何交换行和列，0和1的个数都是不会变化的，再看看长度为奇数的棋盘，比如3:
1 0 1
0 1 0
1 0 1
或者：
0 1 0
1 0 1
0 1 0
我们发现对于长度为奇数的棋盘，各行的0和1个数不同，但是还是有规律的，每行的1的个数要么为 n/2，要么为 (n+1)/2，这个规律一定要保证，不然无法形成棋盘。
还有一个很重要的规律，我们观察题目给的第一个例子，如果我们只看行，我们发现只有两种情况 0110 和 1001，如果只看列，只有 0011 和 1100，我们发现不管棋盘有多长，都只有两种情况，而这两种情况上各位上是相反的，只有这样的矩阵才有可能转换为棋盘。那么这个规律可以衍生出一个规律，就是任意一个矩形的四个顶点只有三种情况，要么四个0，要么四个1，要么两个0两个1，不会有其他的情况。那么四个顶点亦或在一起一定是0，所以我们判断只要亦或出了1，一定是不对的，直接返回-1。之后我们来统计首行和首列中的1个数，因为我们要让其满足之前提到的规律。统计完了首行首列1的个数，我们判断如果其小于 n/2 或者大于 (n+1) / 2，那么一定无法转为棋盘。我们还需要算下首行和首列跟棋盘位置的错位的个数，虽然 01010 和 10101 都可以是正确的棋盘，我们先默认跟 10101 比较好了，之后再做优化处理。
最后的难点就是计算最小的交换步数了，这里要分n的奇偶来讨论。如果n是奇数，我们必须得到偶数个，为啥呢，因为我们之前统计的是跟棋盘位置的错位的个数，而每次交换行或者列，会修改两个错位，所以如果是奇数就无法还原为棋盘。举个例子，比如首行是 10001，如果我们跟棋盘 10101 比较，只有一个错位，但是我们是无法通过交换得到 10101的，所以我们必须要交换得到 01010，此时的错位是4个，而我们通过 n - rowDiff 正好也能得到4，这就是为啥我们需要偶数个错位。如果n是偶数，那么就不会出现这种问题，但是会出现另一个问题，比如我们是 0101，这本身就是正确的棋盘排列了，但是由于我们默认是跟 1010 比较，那么我们会得到4个错位，所以我们应该跟 n - rowDiff 比较取较小值。列的处理跟行的处理完全一样。最终我们把行错位个数跟列错位个数相加，再除以2，就可以得到最小的交换次数了，之前说过了每交换一次，可以修复两个错位
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; }
My thinking process :
- How do we check if it is possible to transform the board into the chessboard?
- Only 2 kinds of rows + one should be inverse to the other, e.g., one is 0110, another one is 0110 or 1001
- Assume the board N * N,
if N is even, rowOneCnt = N / 2, colOneCnt = N / 2.
if N is odd, rowOneCnt = N / 2, colOneCnt = N / 2 + 1 or rowOneCnt = N / 2 + 1, colOneCnt = N / 2
- How do we count the swaps if it is possible to transform the board into the chessboard?
We count colToMove and rowToMove, (colToMove + rowToMove) / 2 will be the number of swaps in total for each swap will move either two columns or two rows. - How do we count colToMove and rowToMove?
- if elements on top edge or left edge == i % 2, they need to be changed
- we can change either colToMove or N - colToMove, similarly, either rowToMove or N - rowToMove
if N is even, choose the smaller one
if N is odd, we must choose the even one between ToMove or N - ToMove, for each swap will move either two columns or two rows
The complete code is as below :
public int movesToChessboard(int[][] board) {
int N = board.length, colToMove = 0, rowToMove = 0, rowOneCnt = 0, colOneCnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (((board[0][0] ^ board[i][0]) ^ (board[i][j] ^ board[0][j])) == 1) {
return -1;
}
}
}
for (int i = 0; i < N; i++) {
rowOneCnt += board[0][i];
colOneCnt += board[i][0];
if (board[i][0] == i % 2) {
rowToMove++;
}
if (board[0][i] == i % 2) {
colToMove++;
}
}
if (rowOneCnt < N / 2 || rowOneCnt > (N + 1) / 2) {
return -1;
}
if (colOneCnt < N / 2 || colOneCnt > (N + 1) / 2) {
return -1;
}
if (N % 2 == 1) {
// we cannot make it when ..ToMove is odd
if (colToMove % 2 == 1) {
colToMove = N - colToMove;
}
if (rowToMove % 2 == 1) {
rowToMove = N - rowToMove;
}
} else {
colToMove = Math.min(colToMove, N - colToMove);
rowToMove = Math.min(rowToMove, N - rowToMove);
}
return (colToMove + rowToMove) / 2;
}