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

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int MovesToChessboard(int[][] board) {
        int N = board.Length;
        int ans = 0;
        
        foreach (var count in new List<Dictionary<string, int>> { GetCount(board), GetCount(Transpose(board)) }) {
            if (count.Count != 2 || !new List<int>(count.Values).OrderBy(v => v).SequenceEqual(new List<int> { N / 2, (N + 1) / 2 })) {
                return -1;
            }

            var lines = count.Keys.ToList();
            string line1 = lines[0];
            string line2 = lines[1];
            if (!AllOpposite(line1, line2)) {
                return -1;
            }

            List<int> starts = N % 2 == 0 ? new List<int> { 0, 1 } : new List<int> { line1.Count(c => c == '1') * 2 > N ? 1 : 0 };

            ans += starts.Select(start => line1.Where((c, i) => (c - '0') != (i % 2 == start ? 1 : 0)).Count()).Min() / 2;
        }
        
        return ans;
    }

    private Dictionary<string, int> GetCount(int[][] board) {
        var count = new Dictionary<string, int>();
        foreach (var row in board) {
            var key = string.Join("", row);
            if (count.ContainsKey(key)) {
                count[key]++;
            } else {
                count[key] = 1;
            }
        }
        return count;
    }

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

    private bool AllOpposite(string line1, string line2) {
        for (int i = 0; i < line1.Length; i++) {
            if ((line1[i] ^ line2[i]) == 0) {
                return false;
            }
        }
        return true;
    }
}

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