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:

  • 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.

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
    }
    

All Problems

All Solutions