В первой строке записано число N — число строк и столбцов квадратного поля. Дальше записано поле по строкам. Каждая грядка состоит из символов ростка 🌱 или пустой земли 🟫.…
В первой строке записано число N — число строк и столбцов квадратного поля. Дальше записано поле по строкам. Каждая грядка состоит из символов ростка 🌱 или пустой земли 🟫. Определите, есть ли в поле хотя бы два ростка в соседних клетках (по горизонтали или по вертикали). В ответе выведите «нужно», если такие соседи есть и поле нужно проредить, и «не нужно», если нет.
Задача понятна. Нужно проверить квадратное поле размером N x N, где каждая клетка содержит либо росток 🌱, либо пустую землю 🟫. Нужно определить, есть ли пара соседних ростков по горизонтали или вертикали. Если такая пара найдена, вывести нужно, иначе не нужно.
Пошаговое решение (пошаговые объяснения)
- Ввод и представление данных
- Считываем N.
- Далее считываем N строк, каждая строка должна содержать N символов: 🌱 или 🟫.
- Храним поле в виде массива строк или массива символов (например, двумерный массив grid[i][j]).
- Поиск соседей
- Пробегаемся по всем клеткам (i, j).
- Если в клетке (i, j) лежит 🌱, то проверяем двух соседей, чтобы не проверить пару дважды:
- правый сосед: (i, j+1), если j+1 < N и там тоже 🌱, тогда сосед есть — выводим нужна и завершаем.
- нижний сосед: (i+1, j), если i+1 < N и там тоже 🌱, тогда сосед есть — выводим нужна и завершаем.
- Если после проверки всех клеток ни одна пара соседних 🌱 не найдена, выводим не нужно.
- Обоснование корректности
- Мы проверяем каждую пару горизонтальных соседей ровно один раз (за счет проверки правого соседа для каждой клетки) и каждую пару вертикальных соседей ровно один раз (за счет проверки нижнего соседа). Поэтому если существует пара соседних ростков, она обязательно будет обнаружена в ходе обхода. Если не найдена ни одна пара — значит соседних ростков нет.
- Сложность
- В худшем случае приходится проверить все клетки и их правых и нижних соседей: O(N^2) по времени.
- Память: O(1) помимо входного поля (если поле не копируется). Если хранить поле как введено, дополнительной памяти не нужно.
- Пример
- Пример 1 (нет соседних ростков): N = 3 🌱🟫🌱 🟫🌱🟫 🟫🟫🌱 Вывод: не нужно
- Пример 2 (есть горизонтальные соседние 🌱): N = 3 🌱🌱🟫 🟫🌱🟫 🟫🟫🌱 Вывод: нужно
- Альтернатива
- Можно реализовать аналогичный алгоритм, но обходя клетки слева направо сверху вниз и для каждой клетки проверять и правого, и нижнего соседа, чтобы не упустить пары.
- Можно также реализовать через цикл по всем парам соседних клеток (горизонтально и вертикально) и проверить наличие 🌱 в каждой паре, но это чуть медленнее по читаемости, несложно остается тем же O(N^2).
Если хочешь, могу привести готовый псевдокод или реализацию на Python/Java/C++ — скажи язык, и адаптирую под него.
