Минимальный обмен, при котором никакие две соседние ячейки матрицы не имеют одинаковых символов.

Опубликовано: 27 Февраля, 2023

Дана матрица размера N * M . Каждая ячейка матрицы содержит либо «A», либо «B». Обмен определяется как обмен символами между двумя ячейками. Задача состоит в том, чтобы найти минимальное количество обменов, необходимое для перестановки заданной матрицы так, чтобы ни одна соседняя ячейка не содержала одинаковых символов.

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

Примеры:

Input: matrix = {{A, A, B, A}, {B, A, B, A}, {B, B, A, B}}
Output: 2
Explanation: Minimum number of cells whose 
characters got changed are 4 (indexes: ((0, 1), (0, 2), 
(0, 3), (2, 0))). The final matrix is:
A B A B
B A B A
A B A B
Here 2 exchange are done so answer is 2.

Input: matrix = {{A, B}, {B, A}}
Output: 0
Explanation: No two adjacent cell contains same character.

Подход: Задача может быть решена на основе следующей идеи:

The idea is to use odd and even places, put ‘A’ at odd(i.e- row+column is odd) and ‘B’ at even(i.e- row+column is even) places, and calculate the number of exchanges required according to the initial matrix and again use vice versa ( i.e:- B at odd and A at even) and then return in which one required exchanges is minimum.

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте две переменные temp1 и temp2 и предположите, что количество обменов равно temp1 для 'A' в четных местах и temp2 для 'A' в нечетных местах.
  • Запустите вложенный цикл для каждого столбца каждой строки и проверьте, является ли это нечетным или четным местом.
    • Если это ровное место и у него есть «А», увеличьте temp2 .
    • В противном случае увеличьте temp1 и проверьте также наличие нечетных мест.
  • В конце циклов вернуть минимум temp1 и temp2 .

Ниже приведена реализация описанного выше подхода.

Сложность времени: O(N*M) для обхода матрицы
Вспомогательное пространство: O(1), потому что дополнительная память не используется.

РЕКОМЕНДУЕМЫЕ СТАТЬИ