Минимум операций для преобразования двоичной матрицы A в B путем переворачивания подматрицы размера K
Даны две бинарные матрицы A[] и B[] размерности N * M и натуральное число K , задача состоит в том, чтобы найти минимальное число переворачиваний подматрицы размера K , необходимое в матрице A[][] , чтобы преобразовать ее в матрица B[][] . Если преобразовать невозможно, то выведите «-1» .
Примеры :
Input: A[][] = { { ‘1’, ‘1’, ‘1’ }, { ‘1’, ‘1’, ‘1’ }, { ‘1’, ‘1’, ‘1’ } }, B[][] = { { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ } }, K = 3
Output: 1
Explanation:
Following are the operations performed:
Operation 1: Flip the submatrix of size K from indices (0, 0) modifies the matrix A[][] to { { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ } }.
Therefore, the minimum number of flips required is 1.Input: A[][] = { { ‘1’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ } }, B[][] = { { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ } }, K = 3
Output: -1
Подход : данная проблема может быть решена с использованием жадного подхода, идея состоит в том, чтобы пройти заданные матрицы A[][] и B[][] и, если соответствующая ячейка (i, j) имеет другое значение, то перевернуть текущую подматрицу размера K из индексов (i, j) и посчитайте эту операцию переворачивания . После обхода данной матрицы, если существуют такие индексы, что подматрицу размера K нельзя перевернуть, выведите «-1» , так как невозможно преобразовать матрицу A[][] в B[][] . В противном случае выведите количество полученных операций.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N*M*K 2 )
Вспомогательное пространство: O(1)