Задача: 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 {
public:
    int movesToChessboard(vector<vector<int>>& board) {
        int N = board.size(), ans = 0;

        for (auto count : {counter(board), counter(transpose(board))}) {
            if (count.size() != 2 || !sortedEquals(count, {N/2, (N+1)/2})) return -1;

            auto it = count.begin();
            vector<int> line1 = it->first, line2 = (++it)->first;
            if (!allOpposite(line1, line2)) return -1;

            vector<int> starts = (N % 2 == 0) ? vector<int>{0, 1} : vector<int>{(accumulate(line1.begin(), line1.end(), 0) * 2 > N)};

            int minSwaps = INT_MAX;
            for (int start : starts) {
                int swaps = 0;
                for (int i = 0; i < N; i++) {
                    swaps += (line1[i] != (i % 2 == start ? 1 : 0));
                }
                minSwaps = min(minSwaps, swaps / 2);
            }
            ans += minSwaps;
        }

        return ans;
    }

private:
    map<vector<int>, int> counter(const vector<vector<int>>& board) {
        map<vector<int>, int> count;
        for (const auto& row : board) {
            count[row]++;
        }
        return count;
    }

    vector<vector<int>> transpose(const vector<vector<int>>& board) {
        int N = board.size();
        vector<vector<int>> transposed(N, vector<int>(N));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                transposed[j][i] = board[i][j];
            }
        }
        return transposed;
    }

    bool allOpposite(const vector<int>& line1, const vector<int>& line2) {
        for (int i = 0; i < line1.size(); i++) {
            if ((line1[i] ^ line2[i]) == 0) {
                return false;
            }
        }
        return true;
    }

    bool sortedEquals(const map<vector<int>, int>& count, const vector<int>& sortedValues) {
        vector<int> values;
        for (const auto& [key, value] : count) {
            values.push_back(value);
        }
        sort(values.begin(), values.end());
        return values == sortedValues;
    }
};

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