21/11/2024 20:25:34

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1540. Как научить компьютер решать японские кроссворды

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Перебирая все варианты закраски строки, можно увидеть, что некоторые клетки всегда будут раскрашены в черный цвет, а некоторые – в белый. Например, в строке длиной 11 возможно 10 размещений отрезков 1, 4 и 2. Здесь и далее символ '#' означает черную клетку, а символ '.' (точка) – белую:

#.####.##..
#.####..##.
#.####...##
#..####.##.
#..####..##
#...####.##
.#.####.##.
.#.####..##
.#..####.##
..#.####.##

Всегда черными будут 5-я и 6-я клетки строки, остальные могут оказаться как белыми, так и черными (такие клетки будем обозначать символом '?'). Обратите внимание, что несколько раз выполняется размещение отрезков 4 и 2, начиная с 4-й клетки, а также с 5-й клетки. Если анализ этих размещений был уже проведен, то повторная их проверка не дает новой информации. Таким образом, не выполняя повторного анализа, можно существенно ускорить проверку всех размещений, особенно при большом числе отрезков. Если уже известно расположение некоторых черных и белых клеток, то варианты размещений, не соответствующие расположению этих клеток, отбрасываются.

Выполняя такой анализ несколько раз, сначала для всех строк, а затем для всех столбцов, мы постепенно восстановим зашифрованную картинку. Процесс восстановления можно считать законченным, когда исчезнут все ‘?’ или не будет новых изменений. Далее показан процесс решения головоломки, первая картинка каждого шага получается после анализа строк, а вторая – столбцов.

1 шаг

     42   
  24832133
11????????
 3????????
 5???##???
 5???##???
11????????
11????????
22????????
31????????
 5???##???

     42   
  24832133
11????.???
 3??##.???
 5??###???
 5??###???
11??#?.???
11??#..???
22??##.???
31??###???
 5???##???

2 шаг

     42   
  24832133
11????.???
 3.###....
 5??###??.
 5??###??.
11?.#..???
11?.#..???
22..##.?#?
31..###.??
 5???##???

     42   
  24832133
11.#?#.?..
 3.###....
 5?####?..
 5?####?..
11?.#..???
11?.#..???
22..##.?##
31..###.??
 5..?##???

3 шаг

     42   
  24832133
11.#.#....
 3.###....
 5?####?..
 5?####?..
11?.#..???
11?.#..???
22..##..##
31..###.??
 5..?####?

     42   
  24832133
11.#.#....
 3.###....
 5?####...
 5?####...
11?.#....?
11?.#....?
22..##..##
31..###.#?
 5..#####?

4 шаг

     42   
  24832133
11.#.#....
 3.###....
 5#####...
 5#####...
11?.#....?
11?.#....?
22..##..##
31..###.#.
 5..#####.

     42   
  24832133
11.#.#....
 3.###....
 5#####...
 5#####...
11..#....#
11..#....#
22..##..##
31..###.#.
 5..#####.

Во входном файле в первой строке содержится два целых числа `N` и `M`. `N` – количество строк в головоломке (`1\ ≤\ N\ ≤\ 60`), `M` – количество столбцов (`1\ ≤\ M\ ≤\ 70`). Далее следует `N` строк с информацией об отрезках, содержащихся в каждой строке головоломки. Это последовательность натуральных чисел (не более 12 чисел), разделенных одним пробелом и заканчивающаяся 0. Далее следует `M` строк с аналогичной информацией об отрезках, содержащихся в каждом столбце головоломки. Все головоломки, использующиеся для тестирования, имеют решение и оно единственное. Кроме того, все использованные головоломки могут быть решены с помощью указанного итерационного алгоритма, без использования перебора вариантов с откатом.

В выходной файл вывести решение головоломки (`N` строк по `M` символов), обозначая символом '#' черную клетку, а символом '.' (точка) – белую.

Пример ввода

Вывод для примера

.#.#....
.###....
#####...
#####...
..#....#
..#....#
..##..##
..###.#.
..#####.