HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Captcha

Section problems

• 10^6
• A + B
• Amuz Deluxe
• C++ и Java
• Captcha
• Hello World
• Radar Defence
• World of Warlcraft
• World of Warlcraft
• 1
• XOR на прямоугольнике
• XOR на прямоугольнике (усложнё...
• You're in the army now

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

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

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

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

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

  • Поворота на угол от 0 до ;
  • Скоса вдоль оси абсцисс с относительным смещением противоположных сторон от -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