| 题目名称 | 1529. [UVa 1094] 修筑水道 |
|---|---|
| 输入输出 | channel.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-02-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 cstdio |
100 | 1.361 s | 18.45 MiB | C++ |
| 关于 修筑水道 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
蛋碎的插头DP（话说什么插头DP不蛋碎了？）……要考虑独立插头的情况（好像也可以用最小表示法？）……
实在懒得搞唯一方案的数据了……输出答案算了 规则有MC的神韵……不过MC是不能四连通，这个是不能八连通 另外，虽然不能八连通地接触到自身，但水道本身要求是四连通的 20191214更新： 我代码里是括号表示法。0-无插头，1-左括号插头，2-右括号插头，3-独立插头。 plug数组是插头状态，exist数组是“是否存在水渠”状态。由于需要考虑当前格子左上角格子（8联通），所以exist数组长度也是列数+1. | ||||
【题目描述】
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上原题有所不同（原题要求输出答案）。