Бассейны стока
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Матрицы и сетки
- Деревья и графы
Дана карта высот — прямоугольная таблица heights. Вода с каждой клетки стекает не более чем в одну из четырёх соседних клеток (север, запад, восток, юг; по диагонали нельзя).
- Если ни один сосед не расположен строго ниже текущей клетки, вода не течёт, и клетка называется стоком.
- Иначе вода течёт к соседу с наименьшей высотой. При равенстве выбирается первое направление из списка: север, запад, восток, юг.
Все клетки, вода с которых прямо или через другие клетки приходит в один и тот же сток, образуют один бассейн. Назовите бассейны строчными латинскими буквами так, чтобы строка, составленная из строк карты сверху вниз, была лексикографически наименьшей: бассейн верхней левой клетки получает a, следующий новый бассейн при обходе по строкам слева направо получает b, и так далее.
Верните список строк той же формы, что и карта: буква бассейна для каждой клетки. Бассейнов не больше 26, размер карты не больше 100 × 100.
Пример: [[9, 6, 3], [5, 9, 6], [3, 5, 9]] → ["abb", "aab", "aaa"].
Источник: Coding Competitions Archive, codejam/2009/qualification_round/watersheds · © Google LLC · Apache-2.0 · условие переведено и дополнено