A Japanese puzzle or nonogram is a problem where one must draw a picture onto a grid on the basis of hints given at the left and top sides of the grid. The picture below shows an example of a solved japanese puzzle.
4 1
1 1
41111 11111
17155151511711171171
3 ...###..............
3 4 ...###..####........
5 2 ...#####....##......
3 2 ...###........##....
2 2 ..##............##..
2 5 5 2 ##..#####..#####..##
1 1 1 1 1 1 1 .#..#.#.#..#...#..#.
1 5 1 1 1 .#..#####..#...#..#.
1 1 1 1 1 1 1 .#..#.#.#..#...#..#.
1 5 1 1 1 .#..#####..#...#..#.
1 1 1 1 .#.........#...#..#.
1 1 1 1 .#.........#...#..#.
Each square is painted black or white. In the beginning of each line there are zero or more positive integers. If they are v1 v2 v3 … vn, then that row has first zero or more white squares, then precisely v1 black squares, then at least one white square, then precisely v2 black squares, and so on. That is, between segments of black squares there is at least one white square, and in the beginning and end of the row there may but need not be white squares. Respectively, on top of each column the lengths of the segments of black squares that are in the column are listed starting with the topmost.
The task of the program is to present a solution to the japanese puzzle given as input, or tell that it has no solution. If the puzzle has many solutions, the program may freely choose which solution it prints.
Solving japanese puzzles is probably an NP-complete problem. (That it is has been proven in a japanese departmental report, but at the time of writing this it seemed that the result has not been presented in any refereed scientific publication.) In practice this means that every algorithm that solves the problem must sooner or later revert to systematic search. It is, however, easy to invent heuristics that significantly speed up finding the solution. Your program must use at least one heuristics.
The input consists of natural numbers. It consists of the following parts:
<The input> ::= <number of rows> <number of columns> <number of row hints> <number of column hints> <Hints> <Hints> <Hints> ::= <Hint group>* <Hint group> ::= <hint>* <zero>
There is one hint group for each row, and similarly for the columns. First the hint groups for the rows are listed starting with the top row, and then for the columns starting from the left. A hint is a positive integer. The end of a hint group is recognized by a zero (0) in the input.
The number of row hints is the total number of hints that apply to rows, that is, the number of numbers in the first <Hints> part that are greater than zero. Similarly the number of column hints is the total number of hints that apply to columns.
If the input has no solution, the program must print – and end of line (C++ \n). Otherwise the program must print one solution (it does not matter which one) as a grid such that in the place of a black square the program prints # and in the place of a white square ., like in the picture above (but without the hints). At the end of every line the program must print end of line. There must be no other characters in the output, not even spaces or extra end of lines. The rule in the general instructions that forbids lines that are longer than 72 characters needs not be obeyed.