OI题库

【题目描述】

Joe，前编程冠军，最终买了一座农场。不不不，他可没病。他只是用编程大赛的一大笔奖金买了他祖先的农场。他希望现在退休，用余生照顾奶牛（由于某些原因，他现在认为自己是奶牛方面的专家）。

不幸的是，Joe简单的野心很难实现。他的农场位于北方，气候寒冷——对于牛来说太冷了！更糟糕的是，这里的气候干燥，不适合农作物生长。Joe现在意识到他必须为他的农场建立一套灌溉系统。这套系统涉及到将一部分河水引入穿过他农场的一条长而蜿蜒的水道。因为离水道最近的谷物将茁壮成长，因此水道越长越好。

他的农场是一块矩形土地，被分割成单位正方形。每个单位正方形中是泥土（由'.'表示）或一块不可移动的石头（由'#'表示）。一格宽的灌溉水道从左上角进入他的农场，从右下角离开。显然，水道不能穿过石头。重要的是，水道不能接触到自身，哪怕一个角也不行（否则水会渗出去走一条捷径）。图3和图4展示了两个接触到自身的例子。

不幸的是，Joe已经不再擅长编程。他找到了一个简单的算法，但它的时间复杂度太大。你能帮助他计算水道的最长长度吗？

【输入格式】

输入文件包含多组数据。

每组数据的第一行有两个正整数：农场的行数r（2<=r<=20）和农场的列数c(2<=c<=9)。

接下来的r行每一行有一个长度为c的字符串，这些字符串描述了Joe的农场。

输入结束标志为一行两个0.

【输出格式】

对每组数据，输出数据的编号（从1开始）。然后输出一行，即水道的最长长度。

【样例输入】

3 3

.#.

...

.#.

6 7

.......

.......

.......

....#..

.......

.#.....

0 0

【样例输出】

Case 1:

5

Case 2:

26

【提示】

样例中最长水道的具体形状（其中'C'代表水道）：

Case 1:

C#.

CCC

.#C

Case 2:

CCCCCCC

......C

CCCCCCC

C...#..

CCC.CCC

.#CCC.C

本题的输出格式和UVa上原题有所不同（原题要求输出答案）。

【来源】

UVa1094 Channel