TransformToChessboard [source code]
public class TransformToChessboard {
static
/******************************************************************************/
class Solution {
public int movesToChessboard(int[][] board) {
int N = board.length;
int[] rows = new int[N];
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < N; j++) {
if (board[i][j] != 1 && board[i][j] != 0)
return -1;
sum = (sum << 1) + board[i][j];
}
rows[i] = sum;
}
int row_swap_num = validateAndCount (rows);
if (row_swap_num < 0)
return -1;
for (int j = 0; j < N; j++) {
int sum = 0;
for (int i = 0; i < N; i++)
sum = (sum << 1) + board[i][j];
rows[j] = sum;
}
int col_swap_num = validateAndCount (rows);
return col_swap_num < 0 ? -1 : row_swap_num + col_swap_num;
}
int validateAndCount (int[] rows) {
Arrays.sort (rows);
int N = rows.length, lo = 0, hi = N - 1;
while (lo < N && rows[lo] == rows[0])
lo++;
while (hi >= 0 && rows[hi] == rows[N - 1])
hi--;
// Only two kinds of rows
if (hi + 1 != lo)
return -1;
int lo_cnt = lo, hi_cnt = N - 1 - hi;
// should be roughly equal numbers of two numbers
if (hi_cnt - lo_cnt > 1 || lo_cnt - hi_cnt > 1)
return -1;
int bit_mask = (1 << N) - 1;
// two numbers should be inverse of each other: has to use XOR, can't use OR or AND
if ((rows[0] ^ rows[N - 1]) != bit_mask)
return -1;
int k = rows[0], res = N, bit_count = Integer.bitCount (k);
if ((N & 1) == 0 || bit_count * 2 < N)
res = Math.min (res, Integer.bitCount (k ^ 0xAAAAAAAA & bit_mask) / 2);
if ((N & 1) == 0 || bit_count * 2 > N)
res = Math.min (res, Integer.bitCount (k ^ 0x55555555 & bit_mask) / 2);
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
TransformToChessboard.Solution tester = new TransformToChessboard.Solution();
int[][][] inputs = {
{{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}}, {{2}},
};
}
}
完全没有思路的题目;
大概理解了editorial的思路之后, 模仿着写了上面的代码, 最后的速度是12ms (NA). 我这个写法主要是想避免使用collection, 来在OJ这里占点便宜;
总体来说题目思路还是理解了, 最后几个算法看下来, 我感觉还是awice的editorial组织最好看;
editorial
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.
哪两种? 不懂; 知道了, 这题我审题的时候丢掉了一个关键的条件(如果连人逻辑都找不到的时候, 尝试考虑一下是不是读题漏了信息):
a board where no 0s and no 1s are 4-directionally adjacent
我当时自己写的时候, 一直担心的一个东西, 就是比如0 0 0 1 0这样, 实际上1的数量并不是max possible, 这样就有很多的uncertainty. 但是当时没有找到思路来排除这个uncertainty; 实际上这个排除的线索就藏在题目里面;
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.
这个01交替的性质是一个重要的observation, 我没有得到;
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.)
这个row swap and col swap: order independent的性质, 是不是一个普适性的性质? 首先, 怎么分析? 假如一个row swap和一个col swap以任何顺序发生, 最后肯定是发生了, 真正可能受到order影响的, 只有两个row和两个col的四个交点; 这两个row和两个col上的其他点, 都只参加了两个swap当中的一个, 所以order不可能对他们有影响;
然后你自己试一下就知道了;
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].
所以这些hard题, 真的不是上手就能直接乱写的, 往往要先把题目的意思思考的很清楚, 然后才能开始写一个算法;
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].
读到这里, 我发现这个sub task其实我也不会;
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.
class Solution {
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;
}
}
注意看上面的代码, 原来set也可以用get by index;
另外你注意他analyze的思路, 他并不是一开始count的时候就在判断01交替, 而是最后一起判断: 数量为2并且等分, 然后xor出来要是全1;
Python版本短的过分了:
class Solution(object):
def movesToChessboard(self, board):
N = len(board)
ans = 0
# For each count of lines from {rows, columns}...
for count in (collections.Counter(map(tuple, board)),
collections.Counter(zip(*board))):
# If there are more than 2 kinds of lines,
# or if the number of kinds is not appropriate ...
if len(count) != 2 or sorted(count.values()) != [N/2, (N+1)/2]:
return -1
# If the lines are not opposite each other, impossible
line1, line2 = count
if not all(x ^ y for x, y in zip(line1, line2)):
return -1
# starts = what could be the starting value of line1
# If N is odd, then we have to start with the more
# frequent element
starts = [+(line1.count(1) * 2 > N)] if N%2 else [0, 1]
# To transform line1 into the ideal line [i%2 for i ...],
# we take the number of differences and divide by two
ans += min(sum((i-x) % 2 for i, x in enumerate(line1, start))
for start in starts) / 2
return ans
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 (NW xor NE) == (SW xor SE), where xor is exclusive or. Here we call it validness property.
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.
@lee215 The validness property I defined is indeed the necessary condition of a valid swap of the chessboard. There exists boards which satisfy validness property but are not valid swaps of the chessboard. My point here is that we only need to consider the first column when we’re swapping rows.
In your example when we’re considering the first column, we would find that it’s not possible to make the first column valid. According to my step 2 we return -1 in such case.
Btw what do you mean by the term “saffies pas”? I googled it but failed to find what you mean.
@hiiwave
When you said “Here we call it validness property”, it thought it would be enough to check if we could make it a chessboard finally.In your step2, it contains 2 different steps in fact (at least in my solution):
- property check: Check if we can make the first colume valid by row swap.()
- (count) If we can, find minimum row swap number.
In my opinion, the key point you mentioned is a good idea and it is easy to understand. So I add this part to my solution:
My original one:
if len(set(map(tuple, b))) != 2: return -1 if len(set(map(tuple, zip(*b)))) != 2: return -1Your idea:
for i in range(N): for j in range(N): if b[0][0]^b[i][0]^b[0][j]^b[i][j]: return -1Here is the whole solution: https://discuss.leetcode.com/topic/120358
这个四xor的做法, 在contest里面还真看到, 看来这个chess board问题还是不少人熟悉的;
Two conditions to help solve this problem:
- In a valid chess board, there are 2 and only 2 kinds of rows and one is inverse to the other.
For example if there is a row 01010011 in the board, any other row must be either 01010011 or 10101100.
The same for columns
A corollary is that, any rectangle inside the board with corners top left, top right, bottom left, bottom right must be 4 zeros or 2 ones 2 zeros or 4 zeros.- Another important property is that every row and column has half ones. Assume the board is N N:
If N = 2K, every row and every column has K ones and K zeros.
If N = 2*K + 1, every row and every column has K ones and K + 1 zeros or K + 1 ones and K zeros.Since the swap process does not break this property, for a given board to be valid, this property must hold.
These two conditions are necessary and sufficient condition for a valid chessboard.Once we know it is a valid cheese board, we start to count swaps.
Basic on the property above, when we arange the first row, we are actually moving all columns.I try to arrange one row into 01010 and 10101 and I count the number of swaps.
- In case of N even, I take the minimum swaps, because both are possible.
- In case of N odd, I take the even swaps.
Because when we make a swap, we move 2 columns or 2 rows at the same time.
So col swaps and row swaps should be even here.
C++:
class Solution {
public:
int movesToChessboard(vector<vector<int>>& b) {
int N = b.size(), rowSum = 0, colSum = 0, rowSwap = 0, colSwap = 0;
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j)
if (b[0][0]^b[i][0]^b[0][j]^b[i][j]) return -1;
for (int i = 0; i < N; ++i) {
rowSum += b[0][i];
colSum += b[i][0];
rowSwap += b[i][0] == i % 2;
colSwap += b[0][i] == i % 2;
}
if (N / 2 > rowSum || rowSum > N / 2 + N % 2) return -1;
if (N / 2 > colSum || colSum > N / 2 + N % 2) return -1;
if (N % 2) {
if (colSwap % 2) colSwap = N - colSwap;
if (rowSwap % 2) rowSwap = N - rowSwap;
}
else {
colSwap = min(N - colSwap, colSwap);
rowSwap = min(N - rowSwap, rowSwap);
}
return (colSwap + rowSwap) / 2;
}
};
Java:
public int movesToChessboard(int[][] b) {
int N = b.length,rowSum=0,colSum=0,rowSwap=0, colSwap=0;
for(int i=0; i<N;++i) for (int j=0; j<N;++j)
if ((b[0][0]+b[i][0]+b[0][j]+b[i][j])%2 == 1) return -1;
for(int i=0; i<N;++i) {
rowSum += b[0][i];
colSum += b[i][0];
if (b[i][0] == i % 2) rowSwap ++;
if (b[0][i] == i % 2) colSwap ++ ;
}
if (N/2 > rowSum || rowSum > N/2+N%2) return -1;
if (N/2 > colSum || colSum > N/2+N%2) return -1;
if (N % 2 == 1) {
if (colSwap % 2 == 1) colSwap = N - colSwap;
if (rowSwap % 2 == 1) rowSwap = N - rowSwap;
}
else {
colSwap = Math.min(N - colSwap, colSwap);
rowSwap = Math.min(N - rowSwap, rowSwap);
}
return (colSwap + rowSwap) / 2;
}
用小rectangle的四个顶点的xor来检查互补, 然后再检查一下1的个数, 就行了, 这样写最后的代码简练很多, 不过我还是感觉这题用bit操作更加readable;
Python:
def movesToChessboard(self, b):
N = len(b)
if any(b[0][0]^b[i][0]^b[0][j]^b[i][j] for i in range(N) for j in range(N)): return -1
if not N/2 <= sum(b[0]) <= N/2+N%2: return -1
if not N/2 <= sum(b[i][0] for i in range(N)) <= N/2+N%2: return -1
col = sum(b[0][i] == i % 2 for i in range(N))
row = sum(b[i][0] == i % 2 for i in range(N))
if N % 2:
if col % 2: col = N - col
if row % 2: row = N - row
else:
col = min(N - col, col)
row = min(N - row, row)
return (col + row) / 2
@lee215 said in Python Solution:
if N % 2: if col % 2: col = N - col if row % 2: row = N - rowcould you explain those three lines of code? thx
@TobeABetterMan
When we make a swap, we move 2 columns or 2 rows at the same time.
So col and row should be even here.
In case N is odd, I check the number needed to be 01010 and 10101. Only one is accepted.
The algorithm is based on counting. A solvable board has each row/column either the same as the first row/column or exactly cell-by-cell reversed color of the first row/column.
In the loop we count for rs and cs, the number of rows/columns being the same as the first row/column, and rm and cm, the number of misplaced rows/columns in the view of the first row/column. If any row/column is found to be neither the same nor reversed color then returns -1 immediately.
Then, for even number n there are two final forms of the first row/column. We compute the minimum swaps of the two cases. For odd number n there is only one final form of the board so we compute the swaps based on the fact that whether the first row/column is in the less or the greater half.
int movesToChessboard(vector<vector<int>>& b) {
int n = b.size();
int rs = 0, cs = 0, rm = 0, cm = 0;
for (int i = 0; i < n; i++) {
bool rf = b[0][0] == b[i][0], cf = b[0][0] == b[0][i];
rs += rf, cs += cf;
rm += rf ^ !(i & 1), cm += cf ^ !(i & 1);
for (int j = 0; j < n; j++)
if ((b[0][j] == b[i][j]) ^ rf || (b[j][0] == b[j][i]) ^ cf)
return -1;
}
if (n % 2 == 0) {
if (rs == n / 2 && cs == n / 2)
return min(rm, n - rm) / 2 + min(cm, n - cm) / 2;
return -1;
}
int res = 0;
if (rs == n / 2)
res += (n - rm) / 2;
else if (rs == n / 2 + 1)
res += rm / 2;
else
return -1;
if (cs == n / 2)
res += (n - cm) / 2;
else if (cs == n / 2 + 1)
res += cm / 2;
else
return -1;
return res;
}
跟editorial基本没有太多的差别;
contest的答案, 有空再看了:
class Solution {
public:
int movesToChessboard(vector < vector < int >> & b) {
int N = b.size();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if ((b[i][0] ^ b[i][j] ^ b[0][0] ^ b[0][j])) return -1;
}
}
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < N; i++) {
if (b[i][0]) cnt1++;
if (b[0][i]) cnt2++;
}
if (cnt1 != N / 2 && cnt1 != (N + 1) / 2) return -1;
if (cnt2 != N / 2 && cnt2 != (N + 1) / 2) return -1;
int res = 0;
int w[2] {};
for (int i = 0; i < N; i++) {
w[b[i][0] ^ (i % 2 == 0)]++;
}
if (N % 2 == 0) {
res += min(w[0], w[1]) / 2;
} else {
if (cnt1 == N / 2) res += w[0] / 2;
else res += w[1] / 2;
}
w[0] = 0, w[1] = 0;
for (int i = 0; i < N; i++) {
w[b[0][i] ^ (i % 2 == 0)]++;
}
if (N % 2 == 0) {
res += min(w[0], w[1]) / 2;
} else {
if (cnt2 == N / 2) res += w[0] / 2;
else res += w[1] / 2;
}
return res;
}
};
这个算法其实跟editorial的方法是一样的; contest时间那么紧张, 这个人分析的这么透彻, 也是不简单了; 你看他w的计算方式:
class Solution {
public int movesToChessboard(int[][] board) {
int one = count(board);
for(int i = 0;i < board.length;i++){
for(int j = 0;j < board.length;j++){
board[i][j] ^= 1;
}
}
int two = count(board);
if(one == -1)return two;
if(two == -1)return one;
return Math.min(one, two);
}
public int count(int[][] a) {
int n = a.length;
int one = 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
one += a[i][j];
}
}
if(one != n*n/2+(n%2))return -1;
int[] ls = new int[n];
int p = 0;
for(int i = 0;i < n;i++){
int ch = 0;
for(int j = 0;j < n;j++){
if((i+j&1) != (a[i][j]^1)){
ch |= 1<<j;
}
}
ls[p++] = ch;
}
int[] vs = Arrays.copyOf(ls, n);
Arrays.sort(vs);
if(vs[0] == vs[n-1]){
return Integer.bitCount(vs[0]) % 2 == 0 ? Integer.bitCount(vs[0])/2 : -1;
}
for(int i = 0;i < n;i++){
if(!(vs[i] == vs[0] || vs[i] == vs[n-1]))return -1;
}
if(vs[0]+vs[n-1] != (1<<n)-1)return -1;
int ret = 999999;
for(int f : new int[]{vs[0], vs[n-1]}){
int bal = 0;
int cum = 0;
for(int j = 0;j < n;j++){
if(ls[j] == f){
bal += j % 2 == 0 ? 1 : -1;
cum += j % 2;
}
}
if(bal == 0 && Integer.bitCount(f^(1<<n)-1) % 2 == 0){
ret = Math.min(ret, Integer.bitCount(f^(1<<n)-1) / 2 + cum);
}
}
return ret == 999999 ? -1 : ret;
}
}
好像还是分析row和col的方法, 没有仔细看, 但是感觉差不多; 不过这个人的解法还是有一点奇葩的地方的, 比如他是先count一次, 然后全部flip之后又重新count一次, 这个flip是什么原理? 而且这两次count的结果, 他是直接取的min, 而不是sum;
日本小哥的解法, 比较长, 到时候有空再看;
class Solution {
public int movesToChessboard(int[][] board) {
int row = gao(board);
int col = gao(t(board));
if (row == -1 || col == -1) return -1;
return row + col;
}
private int[][] t(int[][] board) {
int n = board.length;
int[][] ans = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ans[j][i] = board[i][j];
}
}
return ans;
}
private int gao(int[][] board) {
int n = board.length;
Map<Integer, Integer> cnt = new HashMap<>();
int[] curr = new int[n];
for (int i = 0; i < n; i++) {
curr[i] = 0;
for (int j = 0; j < n; j++) {
curr[i] = (curr[i] << 1) + board[i][j];
}
cnt.put(curr[i], cnt.getOrDefault(curr[i], 0) + 1);
}
if (cnt.size() != 2) return -1;
List<Integer> keys_list = new ArrayList<>(cnt.keySet());
Integer[] keys = new Integer[keys_list.size()];
for (int i = 0; i < keys.length; i++) keys[i] = keys_list.get(i);
if (cnt.get(keys[0]) < cnt.get(keys[1])) swap(keys, 0, 1);
if (cnt.get(keys[0]) - cnt.get(keys[1]) > 1) return -1;
int ans = 0;
for (int i = 0; i < n; i++) {
if (curr[i] != keys[i % 2]) ans++;
}
if (n % 2 == 0) {
int cc = 0;
for (int i = 0; i < n; i++) {
if (curr[i] != keys[((i + 1) % 2)]) cc++;
}
if (cc < ans) ans = cc;
}
return ans / 2;
}
private void swap(Integer[] arr, int i, int j) {
Integer temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
count一次, transpose之后再count一次, 然后求和, 感觉应该是跟editorial差不多的思路;
class Solution {
public:
int movesToChessboard(vector<vector<int>>& board) {
if (board.size() <= 1) {
return 0;
}
int a1 = checkCols(board);
auto board2 = board;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board.size(); j++) {
board2[j][i] = board[i][j];
}
}
int a2 = checkCols(board2);
if (a1 < 0 || a2 < 0) {
return -1;
}
return a1 + a2;
}
int checkCols(vector<vector<int>>& board) {
vector<int> v;
unordered_map<int, int> m;
unordered_map<int, int> c;
int id = 0;
for (int i = 0; i < board.size(); i++) {
int n = 0;
for (int j = 0; j < board.size(); j++) {
n = (n << 1) | board[i][j];
}
if (m.count(n) == 0) {
m[n] = id++;
}
v.push_back(n);
c[n]++;
}
if (id != 2) {
return -1;
}
int a = v[0], b;
for (auto n: v) {
if (n != a) {
b = n;
break;
}
}
int ca = c[a], cb = c[b];
if (abs(ca - cb) > 1) {
return -1;
}
//cout << ca << cb << endl;
int ans = INT_MAX;
if (ca >= cb) {
int k = 0;
for (int i = 0; i < v.size(); i+=2) {
if (v[i] != a) {
k++;
}
}
ans = min(ans, k);
}
if (cb >= ca) {
int k = 0;
for (int i = 0; i < v.size(); i+=2) {
if (v[i] != b) {
k++;
}
}
ans = min(ans, k);
}
return ans;
}
};
Problem Description
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].
- board[i][j] will be only 0s or 1s.
Difficulty:Hard
Total Accepted:507
Total Submissions:1.6K
Contributor:ngoc_lam