Ctrl K

Острова в пределах старой карты

Средняя
Даны две карты одной местности одинакового размера m × n: old_map и new_map. В каждой 1 — суша, 0 — вода. Остров — это группа клеток суши, связанных по сторонам (вверх, вниз, влево, вправо); всё за краем карты — вода. Остров новой карты назовём вложенным, если каждая его клетка является сушей и на старой карте. Верните количество вложенных островов на new_map.
Пример 1
old_map=[[1, 1, 0], [0, 1, 0], [1, 0, 1]], new_map=[[1, 1, 0], [0, 0, 0], [1, 1, 1]] → 1

На новой карте два острова. Верхний {(0, 0), (0, 1)} целиком лежит на суше старой карты. Нижний {(2, 0), (2, 1), (2, 2)} задевает клетку (2, 1), которая на старой карте — вода. Ответ 1.

Пример 2
old_map=[[1, 1], [1, 1]], new_map=[[1, 0], [0, 1]] → 2

Две клетки по диагонали — это два разных острова, и оба лежат на старой суше.

Пример 3
old_map=[[0, 1]], new_map=[[1, 1]] → 0
Ограничения
  • 1 ≤ m, n ≤ 500
  • обе карты имеют размер m × n
  • все клетки — 0 или 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОсушение замкнутых прудов СредняяУчастки суши на карте СредняяСамый большой лесной участок СредняяПоле, разрезанное чертами СредняяСуша без выхода к краю Средняя
загружаем Python…
Вход
old_map=[[1, 1, 0], [0, 1, 0], [1, 0, 1]], new_map=[[1, 1, 0], [0, 0, 0], [1, 1, 1]]
Ожидается
1

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 70 тестов на сервере, включая скрытые.