Понимание формулировки проблемы:
В постановке задачи говорится, что нам дана сетка (матрица) из N строк и M столбцов. Каждая запись в сетке содержит символ # (стена) или . (пол). Все этажи, соединенные горизонтально или вертикально, образуют комнату. Задача состоит в том, чтобы найти количество комнат, присутствующих в сетке.
Пример:
Ввод: N=5, M=8
Выход: 3
Подсказка. Если вы немного попрактиковались в работе с графами и знаете о связных компонентах, вы можете понять эту проблему. Но те, кто не знает термина, все равно могут его решить.
Как решить проблему?
Так как задача состоит в том, чтобы найти количество комнат. Мы видим, что все точки «.», соединенные горизонтально или вертикально, обязательно будут частью одной комнаты. Чтобы проверить, содержит ли ячейка точку или нет, мы должны посетить эту ячейку. Теперь для каждой комнаты, если мы начнем с любой из ячеек (точки), мы сможем посетить все точки этой комнаты.
Приближаемся к подходу
Таким образом, идея, которую мы получили отсюда, заключается в том, что мы должны перебрать сетку, чтобы найти нашу первую точку. Затем мы посетим все точки этой комнаты. Так что, если мы нашли точку, это означает, что она определенно будет вносить свой вклад в комнату. Таким образом, подход будет включать в себя этап, при котором всякий раз, когда мы находим точку, мы увеличиваем количество комнат на 1 и посещаем все точки, которые будут частью одной и той же комнаты.
Мы должны пометить все посещенные точки как посещенные, чтобы они не могли внести свой вклад в другую комнату. Почему? (Попробуйте взять небольшой пример N=1,M=2 Grid = [['.','.']]. Теперь, если мы найдем 1 точку и сделаем количество комнат = 1. Затем посетите все другие точки для той же комнаты. Таким образом, все точки (здесь 2) будут в одной комнате. Но если мы не отметим вторую посещенную точку и продолжим повторять сетку, мы найдем еще одну посещенную точку, а затем она обновит Количество номеров до 2. Это неправильно.
Чтобы сохранить информацию о посещенных ячейках, мы можем использовать другую логическую матрицу того же размера и установить все посещенные ячейки как истинные.
Можно ли избежать инициализации другой матрицы того же размера?
Подсказка. Ячейки со значением "#" бесполезны.
Да, мы можем использовать ту же матрицу, чтобы пометить ячейки как посещенные. Поскольку нам даже не нужно посещать ни одну из ячеек «#». Поэтому мы заменим каждую точку «.» на «#» после посещения. Таким образом, он никогда не будет засчитан в какой-либо другой комнате.
Ограничения: общее количество. ячеек в сетке будет O(N*M), т.е. O(10⁶). Таким образом, мы должны попытаться посетить каждую ячейку O(1) раз, чтобы избежать TLE!
Алгоритм 1:
- Возьмите N, M и сетку в качестве входных данных.
- Инициализировать roomCount = 0
- Для каждой ячейки (i,j):
- Если ячейка содержит точку:
- Вызвать некоторую функцию (i, j), чтобы отметить все посещенные соединенные точки, которые будут вносить свой вклад в эту комнату.
> — Увеличить roomCount на 1. - Номер печатиКоличество.
Мы можем использовать рекурсию для посещения связанных точек. Алгоритм прост (только если вы знаете, как рекурсия), и он также известен как алгоритм поиска в глубину (DFS).
«Я знаю, что в этот момент все кажется тебе безнадежным, но это всего лишь мгновение, а мгновения проходят».
― Блейк Крауч
DFS(i,j):
- Отметьте посещенную ячейку. Матрица[i][j] = ‘#’
- Для всех соседних ячеек(r, c), соединенных ребром непосредственно с текущей ячейкой:
-DFS(r, c)
По-прежнему возникает сообщение о превышении лимита времени или ошибке времени выполнения?
Использование рекурсивного алгоритма может работать одинаково, но существует предел глубины рекурсии, которую мы можем использовать в каждом языке программирования. Худший из них — Java, а самая безопасная глубина — 1000. Будет ли принято вышеприведенное решение? Попробуйте найти максимальную глубину для ввода, на которую может перейти приведенный выше алгоритм.
Подсказка. Какова будет глубина рекурсии, если все ячейки будут точками?
В приведенном выше случае глубина будет O(N*M), т.е. O(10⁶), что неприемлемо для некоторых языков программирования (по крайней мере, для Java). Поэтому в таких случаях всегда рекомендуется использовать итеративный алгоритм. Также известен как BFS поиска в ширину.
BFS(i, j):
- Инициализировать пустую очередь.
- Вставить текущую ячейку в очередь.
- Пока очередь не пуста:
- Опросить ячейку из очереди
- Отметить, что она посещена.
- Для всех соседних ячеек(r, c), соединенных ребром непосредственно с этой ячейкой:< br /> — Вставить в очередь.
Тем не менее, превышен лимит времени?
Будут ли какие-либо проблемы в приведенном выше итеративном (BFS) алгоритме? Да, это не оптимизированная версия BFS для этой проблемы. Почему? Потому что некоторые точки будут вставлены в очередь более 1 раза и размер очереди станет очень большим (Попробуйте небольшой случай, когда все ячейки содержат точки).
Поэтому, чтобы избежать этого, мы будем отмечать посещенные ячейки сразу после их вставки в очередь. Чтобы они не могли быть снова добавлены какой-либо другой соседней ячейкой.
Оптимизированный BFS(i, j):
- Инициализировать пустую очередь.
- Вставить текущую ячейку в очередь. Марк посетил.
- Пока очередь не пуста:
- Опросить ячейку из очереди
- Для всех соседних ячеек(r, c), соединенных непосредственно ребром с этой ячейкой:
— Вставить в очередь. Марк, он посетил.
Временная сложность: O(N*M)
Пространственная сложность: O(min(N,M))
Делитесь своими отзывами в комментариях😶.
Продолжайте писать код!
