P1383. 迷宫

题目描述

金字塔的北部包含一个非常庞大且复杂的迷宫。迷宫被划分为方形区块，每个区块要么被岩石填充，要么是空的。每个空区块的中心地面上还有一个小钩子。ACM发现必须用一根绳子连接两个钩子，绳子需要穿过路径上每个区块的钩子。当绳子固定好后，一扇秘密门就会打开。问题在于我们不知道应该连接哪两个钩子，这意味着所需的绳子长度也是未知的。你的任务是确定给定迷宫可能需要的最大绳子长度。

输入格式

输入包含$T$个测试用例。第一行给出测试用例的数量$T$。每个测试用例以一行两个整数$C$和$R$（$3 \leq C,R \leq 1000$）开始，表示迷宫的列数和行数。接下来是$R$行，每行包含$C$个字符，描述迷宫结构。每个字符是井号(#)或点(.)，井号表示岩石，点表示空区块。只能在相邻区块之间移动（共享一条边的区块），不能对角移动，也不能走出迷宫。

迷宫的设计保证任意两个空区块之间有且仅有一条路径相连。因此，如果我们找到正确的钩子连接，很容易找到连接它们的最长路径。

输出格式

对于每个测试用例，程序必须输出一行，包含句子"Maximum rope length is X."，其中$X$是任意两个空区块之间最长路径的长度（以区块数量计算）。

示例输入

2
3 3
###
#.#
###
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######

示例输出

Maximum rope length is 0.
Maximum rope length is 8.

提示

• 输入数据量可能很大，建议使用scanf读取
• 如果使用递归实现，可能会导致栈溢出（注意C++/C的栈大小通常大于G++/GCC）

来源

Central Europe 1999