Задача: 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. Чтобы убедиться, что мы не добавляем излишне большие элементы.

😎 Решение:

import java.util.*;

class Solution {
    public int movesToChessboard(int[][] board) {
        int N = board.length;
        int ans = 0;
        
        for (Map<int[], Integer> count : Arrays.asList(
                getCount(board),
                getCount(transpose(board))
        )) {
            if (count.size() != 2 || !count.values().containsAll(Arrays.asList(N / 2, (N + 1) / 2))) {
                return -1;
            }

            Iterator<int[]> iterator = count.keySet().iterator();
            int[] line1 = iterator.next();
            int[] line2 = iterator.next();
            if (!allOpposite(line1, line2)) {
                return -1;
            }

            List<Integer> starts = N % 2 == 0 ? Arrays.asList(0, 1) : Arrays.asList(line1[0] * 2 > N ? 1 : 0);

            int minSwaps = Integer.MAX_VALUE;
            for (int start : starts) {
                int swaps = 0;
                for (int i = 0; i < N; i++) {
                    if ((line1[i] - i % 2) % 2 != 0) {
                        swaps++;
                    }
                }
                minSwaps = Math.min(minSwaps, swaps / 2);
            }
            ans += minSwaps;
        }
        
        return ans;
    }

    private Map<int[], Integer> getCount(int[][] board) {
        Map<int[], Integer> count = new HashMap<>();
        for (int[] row : board) {
            count.put(row, count.getOrDefault(row, 0) + 1);
        }
        return count;
    }

    private int[][] transpose(int[][] board) {
        int N = board.length;
        int[][] transposed = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                transposed[j][i] = board[i][j];
            }
        }
        return transposed;
    }

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

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