ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > 110. Способы задания графов и поиск в глубину > задача:


Captcha

Задачи раздела

• Captcha
• Где ключи?
• Граф
• Карта
• Компоненты сильной связности
• Мосты
• Самый сложный предмет
• Сбор букв
• Топологическая сортировка

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Captcha
Captcha
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы предотвратить автоматизацию запросов к различным веб-сервисам (например, для защиты форума от спама), в настоящее время чаще всего используют капчу — простейший тест Тьюринга, задачу, которую просто выполнить человеку и сложно — машине.

В одном из наиболее популярных вариантов капчи нужно определить различные символы (например, цифры) на деформированном изображении. Ваша компания в настоящее время занимается созданием средства для обхода такой капчи. Часть работы уже сделана, а вам поручили реализовать распознавание цифр 7, 8 и 9.

Изображение цифры получено из одного из показанных выше оригинальных изображений (размера 80 × 80 пикселей) путём следующих преобразований:

  • Поворота на угол от 0 до 2?;
  • Скоса вдоль оси абсцисс с относительным смещением противоположных сторон от -100% до 100%;
  • Масштабирования вдоль осей абсцисс и ординат (независимо) с изменением размеров от 20% до 200%.

Закрашенная область изображения связна (между любыми двумя закрашенными пикселями есть путь, проходящий только через закрашенные пиксели, являющиеся соседями по стороне или углу) и не содержит пикселей на границе изображения.

Гарантируется, что цифра на изображении может быть распознана однозначно.

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

Первая строка содержит целые числа N и M (10 ≤ N, M ≤ 200) — высоту и ширину изображения.

Следующие N строк содержат по M символов 'x' или '.', образующих изображение. Символы 'x' соответствуют закрашенным пикселям изображения, символы '.' — незакрашенным.

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

Выведите одно целое число — распознанную цифру.

Примеры

Входные данные
16 20
....................
...xxx..............
..xxxxxx............
..x...xxx...........
..xx...xxx..........
..xx.....x..........
...xx.....xxxx......
....xxx...xxxxxx....
.....xxxxxx..xxxx...
......xxxxx....xx...
.........x.x....xx..
...........xx....x..
............xxx..xx.
.............xxxxxx.
..............xxxx..
....................
Выходные данные
8
Входные данные
17 24
........................
.........xxx............
........xxxxxxxxx.......
........xxxxxxxxxx......
........x....xxxxx......
...............xx.......
..............xxx.......
..............xx........
.............xx.........
............xx..........
...........xxx..........
...........xx...........
..........xx............
.........xxx............
........xxx.............
........xx..............
........................
Выходные данные
7
Входные данные
12 20
....................
.........xxxxxxx....
........xxxx........
.......xxx..........
......xxxxx.........
.....xxx...xx.......
.....xx....xx.......
....xxx....xx.......
....xxx...xxx.......
.....x...xxx........
......xxxxx.........
....................
Выходные данные
9
Для отправки решений необходимо выполнить вход.

www.contester.ru