1576: Fix Image

You are given an image represented as a String[] alteredImage. alteredImage contains only ‘.‘ and ‘#‘ characters, representing white and black pixels, respectively. For the purposes of this problem, two black pixels are directly connected if they share a common edge. Two black pixels A and B are connected indirectly if there exists a path of black pixels A = P₀, P₁, ..., P_k = B, such that P_i and P_{i + 1} are directly connected for all i. A block is a set of black pixels where every two pixels in the set are directly or indirectly connected, and no other black pixel can be added to the block while maintaining that property. A block is considered smooth if for each pair of pixels A and B in the block, there exists a path of black pixels between A and B with length equal to the manhattan distance between A and B. The manhattan distance between two pixels A and B with coordinates (x_A, y_A) and (x_B, y_B), respectively, is the sum of the (absolute) differences of their coordinates(i.e. |x_A - x_B| + |y_A - y_B|). Our friend sent us an image where all the black blocks are smooth. Due to some transmission errors, some black pixels were transmitted as white (but all white pixels remained white). Your task is to retrieve the original image.

The input file consists of several sets of data. Of each set, you are given a integer n, where n is the lines of alteredImage. Then n strings are followed to make up the alteredImage, one string per line. Input ends when n equals to 0. n will be between 1 and 50, inclusive. Each line of alteredImagewill contain between 1 and 50 elements, inclusive. Each line of alteredImagewill contain the same number of characters. alteredImagewill contain only the characters ‘.‘ and ‘#‘.

Find the minimum number of pixels you have to change from white to black so that every black block is smooth and output the original image in the same format as the altered one. The solution with the minimum number of changes will always be unique. Output a blank line after each image.

4
....
.##.
.##.
....
5
.....
.###.
.#.#.
.###.
.....
5
.......
.###...
.#..##.
.###.#.
.....#.
0

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

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

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

In Sample 3, the image consists of two blocks. The right one is smooth. We make the left one smooth by changing the white pixels inside it, but now our image consists of only one block which is not smooth. To make it smooth we need to change one more white square. Because of the huge input data, scanf and printf are recommended strongly.