ZJU/ZOJ 2013 Labyrinth 解题报告

题目大意是在一个矩阵中寻找最长的连续'.’序列的长度。任意两个'.’之间必定存在恰好一条路径。

由“任意两个'.’之间必定存在恰好一条路径”可知这幅图可以转化为树的形式，而题目所求极为树中的最长路。任取一个节点作为根，对树进行一次BFS遍历找到距离其最远的点，再从这个点开始对图进行一次BFS遍历，距离其最远的点与其之间的距离即为树的最长路。或者用TreeDP的形式求其最长的两颗子树的长度之和亦可。

3014581 2008-07-30 20:49:21 Accepted 2013 FPC 00:00.94 6268K IwfWcf@LZOI