← 返回题目列表

AtCoder · fuka_graphcut

G. 图形切割

中文机器翻译题面 查看原题

说明

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=\sum_{(x,y)\in\{W\times H\}}\lambda|X(x,y)-Y(x,y)| +
\sum_{(x,y)\in\{w\times h\}}\sum_{(nx,ny)\in d(x,y)}\frac{\kappa}{2}|X(x,y) - X(nx, ny)|]
.
  • 最好选择 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
...........#...............#..........
...........###..........####..........
...........#####.......####...........
............###############...........
............###############...........
............##############............
.............#############............
............###############...........
...........#################..........
.......#...#################...#......
.......##.##################..##......
........####################.##.......
..........####################........
.........#####..########..#####.......
.......######....#####....######......
......########...#####..########.#....
....#######..#...#####..#..########...
..#########.....#######......#######..
...#######......#######........###....
..####.........#########........###...
...............#########..............
..............##########..............
..............##########..............
...............########...............
...............########...............