Реши задачу на языке swift Яндекс Лавка запускается в городе H. Город H разбит на районы в виде квадратной сетки. Сначала лавки открываются только в некоторых районах (как минимум в одном). Каждый месяц Яндекс Лавка расширяется - открываются новые лавки

24 октября 2025
Программирование

Условие:

Реши задачу на языке swift
Яндекс Лавка запускается в городе H. Город H разбит на районы в виде квадратной сетки. Сначала лавки открываются только в некоторых районах (как минимум в одном). Каждый месяц Яндекс Лавка расширяется - открываются новые лавки во всех соседних районах с уже открытыми лавками. Соседними районами считаются районы, которые соседствую по вертикали или горизонтали. За сколько месяцев Яндекс Лавка будет представлена во всех районах города H?

Формат ввода
Первая строка содержит целое число N - размерность сетки районов 1 <= N <= 1₀00.

Вторая строка содержит целое число M - число лавок на момент запуска сервиса 1 <= M <= 1000000.

Последующие М строк содержит числа i и j, разделенные пробелом, в которых Яндекс.Лавка присутствует на момент запуска сервиса.

Формат вывода
Целое число — количество месяцев, по прошествии которых Яндекс Лавка будет присутствовать во всем городе Н.

Пример 1
Ввод
1
1
0 0
Вывод
0

Пример 2
Ввод
2
1
0 0
Вывод
2

Решение:

Для решения задачи мы можем использовать алгоритм поиска в ширину (BFS), чтобы определить, сколько месяцев потребуется Яндекс Лавке, чтобы охватить все районы города. Давайте разберем решение шаг за шагом.

Шаг 1: Понимание задачи

У нас есть квадратная сетка размером N x N, и в некоторых ячейках уже открыты лавки. Каждый месяц лавки могут открываться в соседних ячейках (по вертикали и горизонтали). Нам нужно узнать, сколько месяцев потребуется, чтобы лавки охватили всю сетку.

Шаг 2: Входные данные

- N: размер сетки (1 = N = 1000)
- M: количество лавок на момент запуска (1 = M = 1000000)
- Далее идут M строк с координатами (i, j) для уже открытых лавок.

Шаг 3: Алгоритм

1. Создаем очередь для BFS и добавляем в нее все начальные позиции лавок.
2. Создаем массив для отслеживания посещенных ячеек.
3. На каждом шаге BFS проверяем соседние ячейки и добавляем их в очередь, если они еще не были посещены.
4. Увеличиваем счетчик месяцев, когда все лавки, которые могут открыться в текущем месяце, будут обработаны.

Шаг 4: Реализация на Swift

Вот пример кода на Swift, который решает задачу:

1. Мы читаем размер сетки и количество лавок, а затем координаты начальных лавок. 2. Создаем массив для отслеживания, какие ячейки уже посещены. 3. Используем BFS для обхода сетки, начиная с начальных лавок. 4. Каждый раз, когда мы обрабатываем уровень BFS, мы увеличиваем счетчик месяцев, если есть новые лавки, которые могут открыться. 5. В конце выводим количество месяцев. - Для ввода программа вернет , так как лавка уже присутствует. - Для ввода программа вернет , так как потребуется два месяца, чтобы охватить всю сетку.