images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
27/04/2024 07:07:04

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1855. Великий пожар Анк-Морпорка

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

История города Анк-Морпорка насчитывает несколько тысячелетий. Неоднократно город подвергался осаде и разграблению, а однажды был почти полностью уничтожен пожаром. Некоторые летописцы считают, что пожар устроил король Сайрон, которому был необходим источник вдохновения для создания поэмы о разрушении античного города Цорта. В летописях описывается, как король стоял на холме в античном хитоне с лютней в руках и, глядя на пылающий город, декламировал строфы своей поэмы.
Предположим, что загоревшийся дом сгорает ровно за один час, а через полчаса после возгорания огонь перекидывается на соседние, еще не загоревшиеся здания. Соседними будем считать здания, соприкасающиеся стеной или углом.
Напишите программу, которая по карте города определит, какое здание нужно поджечь королю Сайрону, чтобы он в процессе пожара смог увидеть максимальное количество одновременно горящих зданий.
Формат ввода
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 50`) – размеры карты. Далее следует `N` строк, содержащих по `M` символов. Символ '.' означает свободную от зданий клетку, а символ '#' – клетку, в которой находится одно здание. Гарантируется, что на карте есть хотя бы одно здание.
Формат вывода
В первой строке вывести одно число – максимальное количество одновременно горящих зданий. Во второй строке вывести два целых числа – номера строки и столбца клетки на карте, в которой находится дом, который нужно поджечь королю. Если существует несколько вариантов для получения максимума, можно вывести любой из них.

Пример ввода

3 6
###.##
.###.#
.#..##

Пример вывода

10
2 4
Примечание к примеру: через час после поджога дома в клетке (2,4) будет гореть 10 домов одновременно, и это зрелище можно будет наблюдать в течение получаса.
loading