UVA1094 Channel
题目描述
Joe，一个前冠军程序员，终于买下了一座农场。不，不，他过得很好；他只是利用了他数量庞大的编程比赛奖金买下了他的祖传农场。他现在希望退休，通过养奶牛度过余生（因为一些原因，他认为自己是一个奶牛专家）。
不幸的是，农夫 Joe 简单的田园梦也无法实现。他的农场气候实在太冷了——对于奶牛太冷了！更糟糕的是，这里的气候很干燥，不适合种植庄稼。Joe 现在意识到他必须为自己的农场制定一个灌溉方案。这个方案将使一条河穿过农场里的一条蜿蜒的渠道。由于作物在渠道旁能茁壮成长，所以渠道越长越好，
他的田地是一个被划分成格子的狭长的矩形。一些格子有泥土，用 `.` 表示；一些有不能移动的石头，用 '#' 表示。一格宽的灌溉渠道从田地左上角进入而从右下角流出，且不通过存在石头的格子。当然，它不能够自交，即使是在角上碰到也不行（这样水会渗透并采取更短的路径）。
下面两种情况的渠道会产生自交：
```
C.CCC
C.C.C
CCC.C
...CC
...C.
...CC
```
```
C...
CCCC
..CC
..C.
..C.
..CC
```
不幸的是，Joe 那最好的编程能力已经被他抛之脑后了。他有一个很简单的解决方法但是太耗时了。你能帮他找到这个渠道的最佳位置吗？
输入格式
输入包含多组数据。
对于每组测试数据：
第一行包含两个整数 $r,c$ 表示行数和列数。
接下来一个 $r$ 行 $c$ 列的矩阵表示 Joe 的田地。
由 `0 0` 结束输入。
输出格式
对于每组数据：
第一行一个字符串，表示数据序号。
接下来一个 $r$ 行 $c$ 列的矩阵表示一种设置渠道的方案，数据保证有解。
每组数据后输出一个空行。
具体细节参照样例。
说明/提示
对于 $100\%$ 的数据：$2\le r\le20,2\le c\le9$。