Запросы на поиск количества связанных компонентов сетки заданных размеров в матрице
Учитывая матрицу mat[][] , содержащую только 0 s и 1 s, и массив query [] , задача для каждого запроса, скажем, k , состоит в том, чтобы найти количество связанных компонентов сетки ( ячейки, состоящие из 1 s ) размера k .
Примечание. Две ячейки соединены, если они имеют общее ребро, направленное вверх, вниз, влево и вправо, а не по диагонали.
Пример:
Input: mat[][] = [[1 1 1 1 1 1],
[1 1 0 0 0 0],
[0 0 0 1 1 1],
[0 0 0 1 1 1],
[0 0 1 0 0 0],
[1 0 0 0 0 0]]
queries[] = [6, 1, 8, 2]
Output: [1, 2, 1, 0]
Explanation: There are 4 connected components of sizes 8, 6, 1, 1 respectively hence the output the queries array is [1, 2, 1, 0]. We can see that the number of connected components of different sizes are marked down in the image:Input: matrix[][] = [[1 1 0 0 0],
[1 0 0 1 0],
[0 0 1 1 0],
[1 1 0 0 0]]
queries[]= [3, 1, 2, 4]
Output: [2, 0, 1, 0]
Explanation: The number of connected components of sizes 3, 2 are 2, 1 all other sizes are zero hence the output array is [2, 0, 1, 0]
Подход: идея состоит в том, чтобы подсчитать и сохранить частоту количества подключенных компонентов всех размеров в неупорядоченной карте с использованием BFS/DFS в сетке, затем мы перебираем массив запросов и назначаем количество подключенных компонентов для каждого заданного размер в массиве.
Ниже приведены шаги для решения проблемы:
- Перебрать матрицу и выполнить BFS из непосещенной ячейки, которая содержит «1».
- Проверьте, содержат ли непосещенные действительные соседние ячейки 1, и поместите эти ячейки в очередь.
- Повторите два вышеуказанных шага для всех непосещенных ячеек, содержащих 1.
- Выведите массив, содержащий количество компонент связности для каждого заданного размера в запросах.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(n*m)
Космическая сложность: O(n*m)