Минимальное количество переворотов, необходимое для того, чтобы бинарная матрица не содержала ни одного пути из левого верхнего угла в правый нижний, состоящего только из 0

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

Для заданной бинарной матрицы mat[][] размерности N*M задача состоит в том, чтобы найти минимальное количество переворотов, требуемых от данной бинарной матрицы, чтобы не существовало никакого пути из верхней левой ячейки в нижнюю. правая ячейка, состоящая только из 0 .

Примеры:

Input: mat[][] = {{0, 1, 0, 0}, {0, 1, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 0}}
Output: 1
Explanation:
Operation 1: Flipping the cell at (1, 0) modifies the given matrix to:
0 1 0 0
1 1 0 0
0 1 0 0
0 0 0 0
After the above operations, there doesn’t exists any path from the top-left cell (0, 0) to the bottom-right cell (3, 3) consisting of only 0s. Therefore, the total number of flips required is 1.
Input: mat[][] = {{0, 0, 0, 0}, {0, 0, 0, 0}}
Output: 2

Подход: данная проблема может быть решена с использованием обхода в глубину по заданной матрице и на основе наблюдения, что существует не более двух переворотов узлов, таких что не существует никакого пути из верхней левой ячейки в нижнюю. правая ячейка, состоящая только из 0 . Идея состоит в том, чтобы выполнить обход DFS от верхней левой ячейки к нижней правой ячейке, чтобы перевернуть не более одного пути и вывести в результате количество успешных вызовов DFS. Выполните следующие шаги, чтобы решить проблему:

Инициализируйте функцию, скажем, DFS(mat, i, j, N, M) , которая принимает текущую ячейку, заданную матрицу и ее размер в качестве параметра, и выполните следующие шаги:
- Если текущая ячейка достигает ячейки (N — 1, M — 1), верните true .
- Обновите значение ячейки в (i, j) до 1 .
- Рекурсивно вызовите функцию DFS во всех четырех направлениях текущей ячейки, т. е. (i + 1, j) , (i, j + 1) , (i – 1, j) и (i, j – 1) , если они существуют.
Если вызов DFS из ячейки (0, 0) возвращает false , то такого пути из верхней левой в нижнюю правую ячейку, состоящего из 0 , не существует. Поэтому выведите 0 в качестве результата и вернитесь из функции.
Опять же, если вызов DFS из ячейки (0, 0) возвращает false , то существует только один путь из верхней левой в нижнюю правую ячейку, состоящий из 0s . Поэтому выведите 1 в качестве результата и вернитесь из функции.
В противном случае выведите 2 в качестве результата.

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

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

Mathematical

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