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

Опубликовано: 22 Сентября, 2022

Даны две бинарные матрицы, A[][] и B[][] из размером N×M, задача состоит в том, чтобы найти минимальное количество перестановок элементов матрицы A, необходимое для преобразования матрицы A в матрицу B . Если это невозможно сделать, то выведите « -1 ».

Примеры :

Input: A[][] = {{1, 1, 0}, {0, 0, 1}, {0, 1, 0}}, B[][] = {{0, 0, 1}, {0, 1, 0}, {1, 1, 0}}
Output: 3
Explanation: 
One possible way to convert matrix A into B is:

  1. Swap the element A[0][0] with A[0][2]. Thereafter the matrix A modifies to {{ 0, 1, 1}, {0, 0, 1}, {0, 1, 0}}.
  2. Swap the element A[0][1] with A[1][1]. Thereafter the matrix A modifies to {{ 0, 0, 1}, {0, 1, 1}, {0, 1, 0}}.
  3. Swap the element A[1][2] with A[2][0]. Thereafter the matrix A modifies to {{ 0, 0, 1}, {0, 1, 0}, {1, 1, 0}}.

Therefore, the total number of moves needed is 3 and also it is the minimum number of moves needed.

Input: A[][] = {{1, 1}, {0, 1}, {1, 0}, {0, 0}}, B[][] = {{1, 1}, {1, 1}, {0, 1}, {0, 0}}
Output: -1 

Наивный подход: эту проблему можно решить с помощью хеширования. Чтобы преобразовать матрицу A в B только заменой, количество установленных битов и неустановленных битов в обеих матрицах должно быть одинаковым. Поэтому сначала проверьте, совпадают ли установленные и неустановленные биты в A с битами B или нет. Если да, то найдите количество позиций, в которых элемент в A не совпадает с элементом в B. Это будет окончательный подсчет.

Эффективный подход: описанный выше подход может быть дополнительно оптимизирован по пространству с помощью наблюдения, которое подсчитывает количество элементов, таких что A[i][j] = 0 и B[i][j] = 1 , и количество элементов, таких что A[i][j] = 1 и B[i][j] = 0 должны быть равны, а минимальное количество необходимых ходов равно полученному счету. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте две переменные, скажем, count10 и count01 , которые подсчитывают количество элементов, таких что A[i][j] = 1 и B[i][j] = 0 , и количество элементов, таких что A{i][j] = 0 и B[i][j] = 1 соответственно.
  • Переберите диапазон [0, N-1], используя переменную i , и выполните следующие шаги:
    • Перебрать диапазон [0, M-1], используя переменную j , и если A[i][j] = 1 и B[i][j] = 0 , то увеличить count10 на 1. В противном случае, если A[i] [j] = 0 и B[i][j] = 1 , затем увеличьте count01 на 1 .
  • Если count01 равно count10 , то в качестве ответа выведите значение count01 . В противном случае выведите -1 в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M).
Вспомогательное пространство: O(1)

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