G - Graph Cut
Editorial
/ 
/ 
Time Limit: 5 sec / Memory Limit: 256 MB
Description
w*hの二値画像がある．この画像上に絵を描いていたのだが誰かがいたずらで部分的に白と黒の画素の値を入れ替えてしまった．元の画像を復元するために色々文献をあさって調べた結果以下の手法を用いることにした．
- ノイズ（いたずらされた画素）は十分少ないとみなす．
- いたずらされた画像の(x,y)の画素の値をY(x,y)とする．
- 復元後の画像の(x,y)の画素の値をX(x,y)とする．
- (x,y)の4近傍(上下左右)をd(x,y)とする．
- 式
![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)|]]( http://fuka5.contest.atcoder.jp/img/other/fuka5/Equ.png)
を考える． - Eを最小にするような復元後の画像を選ぶのがもっとも良い．
- ちなみに，式の前半は画像をあまり変えないように働き，後半部分は色が激しく変化させないように働く．
方法が決まったので，プログラムを書いて絵を復元することにした．
Input
入力は複数のテストケースからなる．入力の終わりは4つの0のみを含んだ行で示される． 各テストケースは以下の形式で与えられる．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
λ,κは0.001刻みで与えられる．
テストケースの1行目には2つの整数h，wと2つの実数λ，κが書かれている． w，hはそれぞれ画像の横幅と縦幅を表し，λ，κは最小化する目的の式Eのパラメータを表す．
続くh行にはそれぞれ.と#で構成される長さwの文字列が書かれている．
Y(x,y)はいたずらされた後の画像の(x,y)の画素の値であり,.が0を表し，#が1を表す．
テストケースの数は1つのファイルにつき300個以下であることが保証されている． また,1つのファイルにつきw*hの合計は8,000以下であることが保証されている．
Output
各テストケースに対して，最小値を与えるEを一行に出力し,次のh行にその最小値を与える画素の割り当てを入力と同じ形式で出力せよ． 誤差は，絶対誤差もしくは相対誤差で10^{-6}まで許容される． 最小値を与える割り当てが複数ある場合はどれを出力しても良い．
Sample Input
10 10 0.4000 0.20 .##...###. .##.####.. .######... .#.#.####. ######.... ##.##..... ....#..... ..####.#.. .#####.##. .#####.##. 25 38 0.5 0.24 ...........#...............#.......... ...........###..........####.......... ....##.....#####.......####........... .....##.....###############.....##.... ............#####.###.#####......#.... ............#########.####............ .....##......#########.###............ ....##......#####.#########........#.. ....#......##.##..####..####.......... .......#...###########.#####...#...... .......##.##################..##...... ........#####.####.##.######.##....... ..........####################........ .........##.##..########..#####....... .......######....##..#....###.##...... ......###.####...##.##..#####.##.#.... ....###..##..#...#####..#..########... ..####..###.....#######......#######.. ...#######......#######........###.... ..####.........##.######........###... ...............###...###.............. ..............#######..#...#...##..... .........#....##########...#....#..... ..#.....##.....########............... ...............########............... 0 0 0 0
Sample Output
11.200000 .##...###. .##.####.. .######... .######... ######.... ##.##..... ....#..... ..####.... .#####.##. .#####.##. 73.540000 ...........#...............#.......... ...........###..........####.......... ...........#####.......####........... ............###############........... ............###############........... ............##############............ .............#############............ ............###############........... ...........#################.......... .......#...#################...#...... .......##.##################..##...... ........####################.##....... ..........####################........ .........#####..########..#####....... .......######....#####....######...... ......########...#####..########.#.... ....#######..#...#####..#..########... ..#########.....#######......#######.. ...#######......#######........###.... ..####.........#########........###... ...............#########.............. ..............##########.............. ..............##########.............. ...............########............... ...............########...............