Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/782.html
782. Transform to Chessboard
Level
Hard
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:
boardwill have the same number of rows and columns, a number in the range[2, 30].board[i][j]will be only0s or1s.
Solution
If it is possible to transform to chessboard, each row and each column must be balanced, which means that the absolute difference between the number of 0’s and the number of 1’s is at most 1 in each row and each column. Otherwise, return -1.
After obtaining the first row’s content, check the other rows’ content as well. Each row must be exactly the same as the first row or exactly the reverse as the first row. Otherwise, return -1.
Then calculate the number of moves according to rows and columns, and return the number of moves.
-
class Solution { public int movesToChessboard(int[][] board) { int[] firstRow = board[0]; if (!isBalanced(firstRow)) return -1; int rows = board.length; int[] flags = new int[rows]; flags[0] = 1; for (int i = 1; i < rows; i++) { if (same(board[i], firstRow)) flags[i] = 1; else if (reverse(board[i], firstRow)) flags[i] = 0; else return -1; } if (!isBalanced(flags)) return -1; int rowSwapNum = getMinSwapNum(flags); int columnSwapNum = getMinSwapNum(firstRow); return rowSwapNum + columnSwapNum; } public boolean same(int[] array1, int[] array2) { int length = array1.length; for (int i = 0; i < length; i++) { if (array1[i] != array2[i]) return false; } return true; } public boolean reverse(int[] array1, int[] array2) { int length = array1.length; for (int i = 0; i < length; i++) { if (array1[i] == array2[i]) return false; } return true; } public boolean isBalanced(int[] array) { int count = 0; for (int num : array) { if (num == 1) count++; else count--; } return Math.abs(count) <= 1; } public int getMinSwapNum(int[] array) { int swapNum1 = 0, swapNum2 = 0; int length = array.length; for (int i = 0; i < length; i++) { if (i % 2 == 0) { if (array[i] == 0) swapNum1++; else swapNum2++; } else { if (array[i] == 1) swapNum1++; else swapNum2++; } } if (swapNum1 % 2 == 0) swapNum1 /= 2; else swapNum1 = -1; if (swapNum2 % 2 == 0) swapNum2 /= 2; else swapNum2 = -1; if (swapNum1 == -1) return swapNum2; else if (swapNum2 == -1) return swapNum1; else return Math.min(swapNum1, swapNum2); } } -
class Solution: def movesToChessboard(self, board: List[List[int]]) -> int: def f(mask, cnt): ones = mask.bit_count() if n & 1: if abs(n - 2 * ones) != 1 or abs(n - 2 * cnt) != 1: return -1 if ones == n // 2: return n // 2 - (mask & 0xAAAAAAAA).bit_count() return (n + 1) // 2 - (mask & 0x55555555).bit_count() else: if ones != n // 2 or cnt != n // 2: return -1 cnt0 = n // 2 - (mask & 0xAAAAAAAA).bit_count() cnt1 = n // 2 - (mask & 0x55555555).bit_count() return min(cnt0, cnt1) n = len(board) mask = (1 << n) - 1 rowMask = colMask = 0 for i in range(n): rowMask |= board[0][i] << i colMask |= board[i][0] << i revRowMask = mask ^ rowMask revColMask = mask ^ colMask sameRow = sameCol = 0 for i in range(n): curRowMask = curColMask = 0 for j in range(n): curRowMask |= board[i][j] << j curColMask |= board[j][i] << j if curRowMask not in (rowMask, revRowMask) or curColMask not in ( colMask, revColMask, ): return -1 sameRow += curRowMask == rowMask sameCol += curColMask == colMask t1 = f(rowMask, sameRow) t2 = f(colMask, sameCol) return -1 if t1 == -1 or t2 == -1 else t1 + t2 -
class Solution { public: int n; int movesToChessboard(vector<vector<int>>& board) { n = board.size(); int mask = (1 << n) - 1; int rowMask = 0, colMask = 0; for (int i = 0; i < n; ++i) { rowMask |= board[0][i] << i; colMask |= board[i][0] << i; } int revRowMask = mask ^ rowMask; int revColMask = mask ^ colMask; int sameRow = 0, sameCol = 0; for (int i = 0; i < n; ++i) { int curRowMask = 0, curColMask = 0; for (int j = 0; j < n; ++j) { curRowMask |= board[i][j] << j; curColMask |= board[j][i] << j; } if (curRowMask != rowMask && curRowMask != revRowMask) return -1; if (curColMask != colMask && curColMask != revColMask) return -1; sameRow += curRowMask == rowMask; sameCol += curColMask == colMask; } int t1 = f(rowMask, sameRow); int t2 = f(colMask, sameCol); return t1 == -1 || t2 == -1 ? -1 : t1 + t2; } int f(int mask, int cnt) { int ones = __builtin_popcount(mask); if (n & 1) { if (abs(n - ones * 2) != 1 || abs(n - cnt * 2) != 1) return -1; if (ones == n / 2) return n / 2 - __builtin_popcount(mask & 0xAAAAAAAA); return (n + 1) / 2 - __builtin_popcount(mask & 0x55555555); } else { if (ones != n / 2 || cnt != n / 2) return -1; int cnt0 = (n / 2 - __builtin_popcount(mask & 0xAAAAAAAA)); int cnt1 = (n / 2 - __builtin_popcount(mask & 0x55555555)); return min(cnt0, cnt1); } } }; -
func movesToChessboard(board [][]int) int { n := len(board) mask := (1 << n) - 1 rowMask, colMask := 0, 0 for i := 0; i < n; i++ { rowMask |= board[0][i] << i colMask |= board[i][0] << i } revRowMask := mask ^ rowMask revColMask := mask ^ colMask sameRow, sameCol := 0, 0 for i := 0; i < n; i++ { curRowMask, curColMask := 0, 0 for j := 0; j < n; j++ { curRowMask |= board[i][j] << j curColMask |= board[j][i] << j } if curRowMask != rowMask && curRowMask != revRowMask { return -1 } if curColMask != colMask && curColMask != revColMask { return -1 } if curRowMask == rowMask { sameRow++ } if curColMask == colMask { sameCol++ } } f := func(mask, cnt int) int { ones := bits.OnesCount(uint(mask)) if n%2 == 1 { if abs(n-ones*2) != 1 || abs(n-cnt*2) != 1 { return -1 } if ones == n/2 { return n/2 - bits.OnesCount(uint(mask&0xAAAAAAAA)) } return (n+1)/2 - bits.OnesCount(uint(mask&0x55555555)) } else { if ones != n/2 || cnt != n/2 { return -1 } cnt0 := n/2 - bits.OnesCount(uint(mask&0xAAAAAAAA)) cnt1 := n/2 - bits.OnesCount(uint(mask&0x55555555)) return min(cnt0, cnt1) } } t1 := f(rowMask, sameRow) t2 := f(colMask, sameCol) if t1 == -1 || t2 == -1 { return -1 } return t1 + t2 } func abs(x int) int { if x < 0 { return -x } return x } func min(a, b int) int { if a < b { return a } return b }