Задача №111406. Морской бой
Вы занимаетесь компьютерной безопасностью. Недавно один из ваших клиентов разработал новый тест, предназначенных для того, чтобы отличить человека от программы. Ваша задача — протестировать его эффективность.
Тест основан на игре «Морской бой». Эта игра проводится на клетчатом поле размером 10 × 10 клеток. Перед началом игры вы должны разместить десять кораблей на этом поле. Каждый корабль задается числом последовательных клеток, расположенных горизонтально или вертикально. Вы должны разместить один четырехклеточный корабль, два трехклеточных, три двухклеточных и четыре одноклеточных корабля. Никакие два корабля не могут иметь общую или соседние по стороне или углу клетки.
После того, как все корабли расставлены, тест продолжается в течение некоторого количества раундов. В каждом раунде выбирается одна клетка, по которой производится стрельба. Корабль тонет, если по каждой его клетке пришлось не менее одного попадания. Тест заканчивается, когда все корабли утонули.
Назовем сложностью расположения кораблей количество раундов, которое потребуется для того, чтобы завершить тест. Идея теста в том, что люди будут создавать более сложные расположения, чем программы.
Вы же выяснили, что порядок, в котором производится стрельба по клеткам, заранее задан, по каждой клетке стреляют ровно один раз. Теперь вам нужно написать программу, которая создает самое сложное расположение кораблей.
Входной файл состоит из десяти строк, каждая из которых содержит десять чисел. Каждое число обозначает номер раунда, в котором по соответствующей клетке будет вестись стрельба. Все числа различны и лежат в диапазоне 1... 100.
Выведите какое-нибудь оптимальное расположение кораблей для данного порядка стрельбы. Пустые клетки должны быть обозначены точкой ('.'), занятые клетки должны быть обозначены решёткой ('#').
1 2 3 4 5 6 7 8 9 10
36 37 38 39 40 41 42 43 44 11
35 64 65 66 67 68 69 70 45 12
34 63 84 85 86 87 88 71 46 13
33 62 83 96 97 98 89 72 47 14
32 61 82 95 100 99 90 73 48 15
31 60 81 94 93 92 91 74 49 16
30 59 80 79 78 77 76 75 50 17
29 58 57 56 55 54 53 52 51 18
28 27 26 25 24 23 22 21 20 19
...####...
..........
#....##...
#.#.....#.
........#.
...###....
.#........
........#.
..#.....#.
.....#..#.