Для того, чтобы затруднить машинное
распознавание букв в системе «CAPTCHA» (Completely Automated Public Turing test to tell Computers and Humans Apart) применяются различные преобразования. Одним из таких преобразований
является «наложение тени» – символ сдвигается и накладывается сам на себя. На
рисунке ниже показан процесс наложения тени на букву «S»
(в примере используется квадрат 8х8).
Примем за начало отсчета верхний
левый угол, и будем отсчитывать горизонтальную координату x слева направо, а вертикальную координату y сверху вниз. Обозначим через (x, y) вектор,
на который было сдвинуто изображение, и назовем его вектором сдвига.
Для приведенного выше рисунка,
вектор сдвига будет (3, 1) – изображение было сдвинуто на 3 точки влево и на 1
вниз.
Исходное изображение (без
наложенной тени) назовем образом, а модифицированное изображение – образом
с тенью.
В дальнейшем будем считать, что у
нас есть изображение, размещенное в квадрате размером 16х16. Условимся также,
что в процессе наложения тени, вектор сдвига выбирается так, что ни одна
закрашенная (черная) точка образа не попадает за пределы исходного квадрата
16х16.
Напишите программу, выполняющую
обратное преобразование: по образу с тенью найти такие вектор сдвига и
образ, что количество закрашенных (черных) точек в образе будет
минимальным. Если таких образов несколько, то ответом будет являться любой из
них.
Ограничения
Вектор сдвига (x, y) ограничен
так, что ни одна черная точка исходного изображения не выходит за пределы
квадрата 16х16.
–15 <= x, y <= 15.
Входные данные
Входной файл содержит образ с тенью
и состоит из 16 строк, каждая из которых содержит ровно по 16 символов. Пустая
(белая) точка обозначается символом «.»
(ASCII = 2Eh), закрашенная
точка обозначается символом «#»
(ASCII = 23h).
Выходные данные
Первая строка выходного файла
содержит два целых числа x и y, разделенных пробелом – вектор сдвига. Далее
следуют 16 строк по 16 символов в каждой – найденный образ, записанный таким же
способом, как во входном файле.
Пример
|
Input
|
Output
|
.###............
#...###.........
#..#...#........
.###............
....###.........
#...#..#........
.###...#........
....###.........
................
................
................
................
................
................
................
................
|
3 1
.###............
#...#...........
#...............
.###............
....#...........
#...#...........
.###............
................
................
................
................
................
................
................
................
................
|
