eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Валидатор к игре в тетрис

Валидатор к игре в тетрис

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Напомним условие задачи Тетрис:

В процессе игры в Тетрис связные фигуры (т. е. связные, если идти по 4-м направлениям) падают вниз в колодец из N строк и 20 столбцов. Каждая фигура помечена уникальной буквой английского алфавита от "A" до "Z". Фигуры, пока они падают, ни двигать, ни вращать нельзя. Ваша программа должна по описанию колодца определить, в каком порядке падали блоки.

Формат входных данных

Первая строка входного файла содержит целое число N (0 ≤ N ≤ 50) — количество строк в колодце. Каждая из следующих строк содержит по 20 символов, каждый из которых — это либо буква от "A" до "Z", либо символ "." (ASCII 46), обозначающий пустую клетку.

Вам требуется написать валидатор тестов к этой задаче.

Входные данные

Входной файл содержит несколько тестов. Каждый тест дан в следующем формате:

Число N (1N50) и N строк из 20 символов каждая.

Символы могут иметь ASCII коды от 32 до 127.

Сумма N по всем тестам не превысит 500000.

Выходные данные

Для каждого теста выведите YES или NO — корректен тест или нет.

Тест считается корректным, если выполнены все следующие условия:

  • Используются только символы "A..Z" и "."

  • Фигура (т.е. множество всех клеток с некоторой буквой) образует связную область.

  • Никакая фигура не "висит в воздухе".

  • Фигуры действительно могли упасть в таком порядке.

Пример

Входные данные #1
6
...........XX.......
..........MMMM......
..........K.........
........KKK.........
.....ZAAA.FFF.......
.....ZZZA..F.B......
2
??..................
??..................
3
AAB.................
ABB.................
AAB.................
3
....................
AA..................
..B.................
1
A..................A
1
ABCDEFGHIJKLMNOPQRST
Выходные данные #1
YES
NO
NO
NO
NO
YES
Автор Сергей Копелиович
Источник Зимняя школа, Харьков 2011, День 5