Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
200. Замок
Компоненты связности, мосты, точки сочлененияОлимпиадные задачи на русском языке
| 02/07/2007 | Лето 2007 - 1 (G) |
| 02/07/2007 | Лето 2007 дорешивание ( 1G) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # -># | | | | # # ############################# # стена | нет стены - нет стены стрелка указывает на стенку, которую надо удалить
На рисунке изображена карта замка. Составить программу, которая вычисляет
- сколько комнат в замке;
- размер самой большой комнаты в замке;
- какую стенку надо удалить, чтобы получить комнату как можно большего размера.
Замок разделен на `m*n\ (2≤m≤50,\ 2≤n≤50)` квадратов. Каждый такой квадрат может иметь от 0 до 4 стен.
Первая строка ввода содержит число `m`, вторая – число `n`. В следующих `m` строках по `n` чисел – карта замка. Каждый квадрат описан числом `p_{ij}\ (0\ ≤\ p_{ij}\ ≤\ 15)`. Это число – сумма для стен квадрата: 1 (=западная стена), 2 (=северная стена), 4 (=восточная стена), 8 (=южная стена). Внутренние стенки определены дважды; южная стена в квадрате (1,1) также обозначена как северная квадрате (2,1). замок всегда имеет по крайней мере две комнаты.
Вывести три строки: в первой строке – число комнат, во второй строке – размер самой большой комнаты, рассчитанный в квадратах, и в третьей строке – предложение, какую стенку удалить. Сначала номер строки, затем номер столбца квадрата рядом со стенкой и в конце – направление компаса ( N, S, E или W), которое указывает на стенку. Можно вывести любой вариант для удаляемой стенки.
Пример ввода
4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13
Пример вывода
5 9 4 1 E
