Проверьте, есть ли в заданной двоичной матрице T непрерывных блоков из нулей или нет.

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

Учитывая бинарную матрицу mat[][] размерности M*N , задача состоит в том, чтобы проверить, существуют ли T непрерывных блоков из 0 или нет, и не менее 2*max(M, N) ячеек со значением 0 или нет. Если найдено верно, то выведите Yes . В противном случае выведите Нет .

 T is defined as the GCD of N and M. A continuous block is defined as the continuous stretch through row-wise or columns-wise or diagonal-wise.

Примеры:

Input: N = 3, M = 4, mat[][] = { {1, 0, 0}, {1, 1, 0}, {0, 0, 0}, {0, 0, 1}}
Output: Yes
Explanation: Matrix has exactly 8 cells with value 0 which is equal to 2*max(N, M )) and there is 1 continuous spot which is equal to GCD of N and M.

Input: N = 3, M = 3, mat[][] = {{0, 0, 1}, {1, 1, 1}, {0, 0, 1}}
Output: No

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

  • Инициализируйте переменную, скажем, черный как 0 и подсчитайте количество ячеек со значением 0 .
  • Если черное меньше, чем равно 2*max(M, N), то выведите No и вернитесь из функции.
  • Инициализируйте переменную, скажем, blackSpots как 0 , чтобы подсчитать количество непрерывных пятен.
  • Итерация по диапазону [0, M) с использованием переменной i и вложенная итерация по диапазону [0, N) с использованием переменной j и если текущая ячейка посетила [i] [j] как ложную и если мат [i] [j] ] равно 0 , затем выполните обход в глубину по заданной матрице с текущей ячейкой, чтобы найти непрерывный сегмент со значением 0 по строкам, по столбцам и по диагонали и увеличить значение blackSpots на 1 .
  • После выполнения вышеуказанных шагов, если значение blackSpots больше, чем gcd(M, N) , выведите Yes . В противном случае выведите Нет .

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


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

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