Московская городская олимпиада школьников по информатике,
2004/05 учебный год
при поддержке компании
Задача L. Кубическая гостиница
| Имя входного файла: | l.in |
| Имя выходного файла: | l.out |
| Максимальное время работы на одном тесте: | 3 секунды |
| Максимальный объем используемой памяти: | 16 мегабайт |
В связи с проведением межпланетного шашечного турнира было принято решение о строительстве орбитальной гостиницы. Она должна была представлять собой большой куб из NxNxN блоков - маленьких кубиков 1x1x1, и каждый блок должен был быть окрашен снаружи со всех сторон в какой-то один цвет. При этом некоторые блоки могли быть покрашены в один и тот же цвет.
Через год были сделаны фотографии гостиницы с каждой из 6 сторон: спереди, слева, сзади, справа, сверху, снизу. За год эксплуатации могло случиться так, что из-за непрочного крепления некоторые блоки, из которых была построена гостиница, оторвались и улетели в открытый космос. Комиссия по восстановлению гостиницы хочет по сделанным снимкам установить максимальное возможное количество оставшихся блоков.
Итак, вам необходимо по видам гостиницы (куба NxNxN, из которого, возможно, выкинуты некоторые кубики 1x1x1) с 6 сторон определить, из какого максимального количества блоков 1x1x1 она может состоять. Может оказаться так, что гостиница состоит из двух или более не связанных между собой частей.
Формат входных данных
В первой строке входного файла находится число N - размер гостиницы (1≤N≤10). На следующих N строках записаны виды гостиницы с 6 сторон (в следующем порядке: спереди, слева, сзади, справа, сверху, снизу). Каждый такой вид представляет собой таблицу NxN, в которой различными заглавными латинскими буквами обозначены различные цвета, а символом "." (точка) - то, что в этом месте можно будет смотреть прямо сквозь гостиницу. Два последовательных вида отделяются друг от друга ровно одним пробелом в каждой из N строк.
Нижняя граница вида сверху соответствует верхней границе вида спереди, а верхняя граница вида снизу - нижней границе вида спереди. Для видов спереди, сзади и с боков верх и низ вида соответствуют верху и низу гостиницы.
Входные данные корректны, то есть во входном файле описано состояние, которое может получиться.
Формат выходных данных
Выведите в выходной файл одно число - искомое максимальное количество оставшихся блоков в гостинице.
Примеры
| l.in | l.out |
3 .R. YYR .Y. RYY .Y. .R. GRB YGR BYG RBY GYB GRB .R. YRR .Y. RRY .R. .Y. |
11 |
2 ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ |
8 |