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);
    }
}

All Problems

All Solutions