Есть матрица (массив массивов) вида
[
[1, 0, 0, 0, 0, 1],
[0, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0],
[1, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 1]
]Нужно реализовать метод, который найдет все острова. Островом считаются 1, которые не примыкают к границам. Диагонали не считаются за соединения.
То есть на выходе должна быть матрица такого вида:
[
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0]
]Как вы бы решали такую задачу?
Доп вопросы:
- Возможно ли решить задачу без аллоцирования памяти? (Стэк константного размера не считается)
- Какая минимально возможная сложность по времени (О-нотация)?
#interview #task #algorithms