Условие:
Напиши код на питоне 3.13.2
C. Опять пожар
ограничение по времени на тест 2 seconds
ограничение по памяти на тест 64 megabytes
вводinput.txt
выводoutput.txt
После ужасающего лесного пожара в Берляндии была реализована программа восстановления леса, по которой были посажены N рядов по M деревьев в каждом, причем настолько ровно, что можно ввести систему координат, в которой j-тое дерево в i-м ряду будет иметь координаты (i, j). Но случилось ужасное, и едва окрепший лес загорелся. И теперь для составления плана эвакуации необходимо найти координаты дерева, которое загорится позже всех.
Возгорание произошло в K точках одновременно, т.е. в начальный момент времени загорелось K деревьев. Каждую минуту огонь перекидывается со всех горящих деревьев на те деревья, которые еще не горят и расстояние от которых до ближайшего горящего дерева равно 1.
Найдите дерево, которое загорится позже всех. Если таких деревьев несколько, выведите любое.
Входные данные
В первой строке входного файла заданы два целых числа N, M (1 ≤ N, M ≤ 2000) — размеры леса. Деревья были посажены во всех точках вида (x, y) (1 ≤ x ≤ N, 1 ≤ y ≤ M), x и y — целые числа.
Во второй строке задано одно целое число K (1 ≤ K ≤ 10) — количество деревьев, горящих в начальный момент времени.
В третьей строке задано K пар целых чисел: x1, y1, x2, y2, ..., xk, yk (1 ≤ xi ≤ N, 1 ≤ yi ≤ M) — координаты точек возгорания. Гарантируется, что все точки возгорания различны.
Выходные данные
Выведите одну строку, содержащую два целых числа x и y, записанные через пробел, — координаты дерева, которое загорится последним. Если таких деревьев несколько, выведите любое из них.
Примеры
Входные данныеСкопировать
3 3
1
2 2
Выходные данныеСкопировать
1 1
Входные данныеСкопировать
3 3
1
1 1
Выходные данныеСкопировать
3 3
Входные данныеСкопировать
3 3
2
1 1 3 3
Выходные данныеСкопировать
2 2
Решение:
Для решения задачи о распространении огня в лесу, мы можем использовать алгоритм поиска в ширину (BFS). Этот алгоритм хорошо подходит для поиска кратчайшего пути в графах, что в нашем случае соответствует времени, необходимому для того, чтобы огонь достиг определенного дерева.
Шаги решения:
1. Чтение входных данных: Сначала мы считываем размеры леса, количество горящих деревьев и их координаты.
2. Инициализация: Создаем матрицу для хранения времени, когда каждое дерево загорится. Инициализируем время для горящих деревьев как 0, а для остальных деревьев как бесконечность.
3. BFS: Используем очередь для BFS, начиная с горящих деревьев. На каждой итерации мы проверяем соседние деревья (вверх, вниз, влево, вправо) и обновляем их время загорания, если текущее время + 1 меньше уже записанного времени.
4. Поиск последнего загоревшегося дерева: После завершения BFS, мы ищем дерево с максимальным временем загорания.
Код на Python:
- Мы используем для реализации очереди BFS. - Время загорания для каждого дерева инициализируется как бесконечность, кроме тех, которые уже горят. - Мы проверяем соседние деревья и обновляем их время загорания, если это необходимо. - В конце мы ищем дерево с максимальным временем загорания и выводим его координаты. Этот код будет работать эффективно в пределах заданных ограничений.