Почему это работает
- explore добавляет в seen каждую клетку суши, до которой можно дойти через стороны, в любую сторону, в том числе вверх. Поэтому один вызов охватывает весь остров, как бы он ни изгибался.
- Проход начинает новый остров только на суше, которой ещё нет в seen, поэтому каждый остров считается один раз: на его первой клетке по строкам.
- Каждая клетка суши попадает в seen один раз, и explore запускается на ней один раз, поэтому обход не зацикливается.
Сложность
Время O(rows × cols): каждую клетку проходим один раз, и каждую клетку суши обходим один раз. Память O(rows × cols) на seen и, в худшем случае, на стек вызовов глубиной в один длинный остров.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗