Задача: 782. Transform to Chessboard
Сложность: hard

Дана бинарная сетка размером n x n. В каждом ходе можно поменять местами любые две строки или любые два столбца.

Верните минимальное количество ходов, чтобы преобразовать сетку в шахматную доску. Если задача невыполнима, верните -1.

Шахматная доска — это доска, на которой ни один 0 и ни одна 1 не соприкасаются друг с другом по вертикали и горизонтали.

Пример:

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.
The first move swaps the first and second column.
The second move swaps the second and third row.

👨‍💻 Алгоритм:

1⃣Для каждого набора строк (и столбцов соответственно) убедитесь, что существует только 2 вида линий в правильных количествах, которые являются противоположностями друг друга.

2⃣Затем для каждой возможной идеальной трансформации этой линии найдите минимальное количество перестановок, чтобы преобразовать эту линию в её идеальную и добавьте это к ответу. Например, [0, 1, 1, 1, 0, 0] имеет два идеала [0, 1, 0, 1, 0, 1] или [1, 0, 1, 0, 1, 0]; но [0, 1, 1, 1, 0] имеет только один идеал [1, 0, 1, 0, 1].

3⃣В Java мы используем целые числа для представления строк как двоичных чисел. Мы проверяем количество различий с [1, 0, 1, 0, 1, 0, ...] с помощью побитового исключающего ИЛИ с 0b010101010101.....01 = 0x55555555. Чтобы убедиться, что мы не добавляем излишне большие элементы.

😎 Решение:

class Solution {
    movesToChessboard(board) {
        const N = board.length;
        let ans = 0;
        
        for (const count of [this.getCount(board), this.getCount(this.transpose(board))]) {
            const values = Object.values(count).sort((a, b) => a - b);
            if (values.length !== 2 || values[0] !== Math.floor(N / 2) || values[1] !== Math.floor((N + 1) / 2)) {
                return -1;
            }

            const [line1, line2] = Object.keys(count);
            if (!this.allOpposite(line1, line2)) {
                return -1;
            }

            const starts = N % 2 === 0 ? [0, 1] : [line1.split('1').length * 2 > N ? 1 : 0];
            
            ans += Math.min(...starts.map(start => {
                return line1.split('').reduce((sum, c, i) => sum + ((c - '0') !== (i % 2 === start ? 1 : 0)), 0);
            })) / 2;
        }
        
        return ans;
    }

    getCount(board) {
        const count = {};
        for (const row of board) {
            const key = row.join('');
            count[key] = (count[key] || 0) + 1;
        }
        return count;
    }

    transpose(board) {
        const N = board.length;
        const transposed = Array.from({ length: N }, () => Array(N).fill(0));
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
                transposed[j][i] = board[i][j];
            }
        }
        return transposed;
    }

    allOpposite(line1, line2) {
        for (let i = 0; i < line1.length; i++) {
            if ((line1[i] ^ line2[i]) === 0) {
                return false;
            }
        }
        return true;
    }
}

Ставь 👍 и забирай 📚 Базу знаний