Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1845. Место встречи
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (H) |
| 03/07/2019 | Лето 2019 - 2 (C) |
| 09/07/2021 | Лето 2021-6 (командное) (F) |
| 08/07/2022 | Лето 2022-6 (командное) (F) |
| 10/12/2022 | «Базовая олимпиадная подготовка» (second level) - Поиск в ширину (BFS) (проводит novink) (D) |
| 14/12/2022 | Курс I - BFS (проводит BOGAT) (D) |
| 11/12/2023 | Графы: BFS (проводит BOGAT) (D) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Петя должен срочно встретиться со своими друзьями. Он обзвонил друзей и узнал их местонахождение.
У каждого из друзей Пети на телефоне есть карта местности, разбитая на клетки. Пете нужно выбрать место
для встречи, в которое все смогут попасть за минимальное время, и разослать его координаты друзьям.
За одну секунду Петя и его друзья могут перейти из клетки, в которой находятся, в соседнюю по
горизонтали или вертикали клетку, свободную от препятствий. В одной клетке может находиться
любое количество людей одновременно. Пришедшие на место встречи раньше других должны подождать всех остальных.
Напишите программу, определяющую координаты места встречи и минимальное время, которое потребуется для того,
чтобы Пети и его друзья смогли до него добраться.
Формат ввода
Первая строка ввода содержит три целых числа `N`, `M` и `K` (`2\ ≤\ N,M\ ≤\ 1000`, `2\ ≤\ K\ ≤\ 9`).
Далее следует `N` строк, содержащих по `M` символов — карта местности. Символом '#' на карте
обозначены препятствия и здания, символом '.' – свободная клетка, цифрой от 1 до `K` – текущее
местонахождение Пети и его друзей, также свободная от препятствий клетка. Гарантируется, что любой из
друзей может дойти до Пети двигаясь только по свободным клеткам.
Формат вывода
В первой строке вывести одно целое число – минимальное время до встречи. Во второй строки
вывести координаты места встречи — номер строки и номер столбца через пробел. Если существует
несколько вариантов для места встречи, то можно вывести любой из них.
Пример ввода
3 4 3 1..2 ###. 3...
Пример вывода
4 2 4
