说明
w*h的二值图像。 I was drawing on this image, but someone mischievously swapped the values of the white and black pixels.在查阅各种文档恢复原始图像后,我决定使用以下方法。
- Noise (tampered pixels) is considered to be sufficiently small.
- Let Y(x,y) be the value of the pixel at (x,y) in the pranked image.
- Let the value of the pixel (x,y) of the restored image be X(x,y).
- 设 d(x,y) 为 (x,y) 的四个邻域(上、下、左、右)。 Consider
- 式
. - 最好选择 E 最小化的恢复图像。
- 顺便说一句,公式的前半部分可以使图像不会发生太大变化,后半部分可以使颜色不会发生太大变化。
决定了方法后,我决定编写一个程序来恢复图片。
输入
The input consists of multiple test cases. The end of the input is indicated by a line containing only four zeros. 每个测试用例均按以下格式给出。h w λ κ Y(1,1)Y(2,1)...Y(w,1) Y(1,2)Y(2,2)...Y(w,2) ... Y(1,h)Y(2,h)...Y(w,h)
- 1<=h,w<=50
- 0.000<λ,κ<=1.000
λ and κ are given in steps of 0.001.
测试用例的第一行包含两个整数h,wand two real numbers λ and κ are written. w,h分别表示图像的宽度和高度,λ和κ表示作为最小化目标的方程E的参数。 每条
继续h行都有
长度由.和
将其放在#组成
写入字符串w。
Y(x,y)是图像被篡改后的像素(x,y)的值,.代表0,#代表 1。
每个文件的测试用例数量保证不超过300个。 Also, per filew*h的总和保证小于或等于 8,000。
输出
对于每个测试用例,输出在一行上给出最小值的 E,然后h以与输入相同的格式输出赋予该行最小值的像素分配。 该误差可以是绝对误差或相对误差。 最多允许10^{-6}。 如果有多个赋值都给出最小值,则可以输出任意一个。
Sample Input 由
10 10 0.4000 0.20 .##...###. .##.####.. .######... .#.#.####. ######.... ##.##..... ....#..... ..####.#.. .#####.##. .#####.##. 25 38 0.5 0.24 ...........#...............#.......... ...........###..........####.......... ....##.....#####.......####........... .....##.....###############.....##.... ............#####.###.#####......#.... ............#########.####............ .....##......#########.###............ ....##......#####.#########........#.. ....#......##.##..####..####.......... .......#...###########.#####...#...... .......##.##################..##...... ........#####.####.##.######.##....... ..........####################........ .........##.##..########..#####....... .......######....##..#....###.##...... ......###.####...##.##..#####.##.#.... ....###..##..#...#####..#..########... ..####..###.....#######......#######.. ...#######......#######........###.... ..####.........##.######........###... ...............###...###.............. ..............#######..#...#...##..... .........#....##########...#....#..... ..#.....##.....########............... ...............########............... 0 0 0 0
示例输出
11.200000 .##...###. .##.####.. .######... .######... ######.... ##.##..... ....#..... ..####.... .#####.##. .#####.##. 73.540000 ...........#...............#.......... ...........###..........####.......... ...........#####.......####........... ............###############........... ............###############........... ............##############............ .............#############............ ............###############........... ...........#################.......... .......#...#################...#...... .......##.##################..##...... ........####################.##....... ..........####################........ .........#####..########..#####....... .......######....#####....######...... ......########...#####..########.#.... ....#######..#...#####..#..########... ..#########.....#######......#######.. ...#######......#######........###.... ..####.........#########........###... ...............#########.............. ..............##########.............. ..............##########.............. ...............########............... ...............########...............