P14848 [ICPC 2022 Yokohama R] Remodeling the Dungeon

Icpca 的女王平静地居住在一座城堡中。一天，她听说许多特工在其他国家活跃，于是开始担忧城堡的安全。 城堡有一个矩形地牢，由 $h$ 行 $w$ 列的正方形房间组成。相邻房间由墙壁隔开。有些墙壁上有门道，使得被隔开的房间可以互通。地牢的入口和出口位于两个对角线的角落房间。地牢的房间构成一棵 **树**，也就是说，从地牢的每个房间到出口房间都有一条唯一的路径可达，该路径上的每个房间仅经过一次。 为了增强城堡的安全，女王想要改造地牢，使得从入口房间到出口房间的路径上的房间数量最大化。她喜欢当前地牢的树状属性，因此必须保留这一特性。由于成本限制，改造只能做两件事：封闭一个现有的门道使其不可用，并在另一面墙（可能是同一面墙）上建造一个新的门道。 你的任务是找到一种改造地牢的方法，以满足女王的需求。

输入由单个测试用例组成，格式如下。 $$ h \ w $$ $$ c_{1,1} c_{1,2} \cdots c_{1,2w+1} $$ $$ c_{2,1} c_{2,2} \cdots c_{2,2w+1} $$ $$ \vdots $$ $$ c_{2h+1,1} c_{2h+1,2} \cdots c_{2h+1,2w+1} $$ $h$ 和 $w$ 表示地牢的大小，每个都是介于 $2$ 到 $500$ 之间（含）的整数。字符 $c_{i,j}$ ($1 \leq i \leq 2h+1$, $1 \leq j \leq 2w+1$) 表示地牢的配置，如下所示： - $c_{2i,2j} = \text{'}.\text{'}$ 对于 $1 \leq i \leq h$ 和 $1 \leq j \leq w$，对应地牢中从北端数第 $i$ 行、西端数第 $j$ 列的房间；这样的房间称为房间 $(i,j)$。 - $c_{2i+1,2j} = \text{'}.\text{'}$ 或 $\text{'}-\text{'}$ 对于 $1 \leq i \leq h-1$ 和 $1 \leq j \leq w$，表示房间 $(i,j)$ 和 $(i+1,j)$ 之间的墙壁；字符 $\text{'}.\text{'}$ 表示该墙有门道，$\text{'}-\text{'}$ 表示没有门道。 - $c_{2i,2j+1} = \text{'}.\text{'}$ 或 $\text{'}|\text{'}$ 对于 $1 \leq i \leq h$ 和 $1 \leq j \leq w-1$，表示房间 $(i,j)$ 和 $(i,j+1)$ 之间的墙壁；字符 $\text{'}.\text{'}$ 表示该墙有门道，$\text{'}|\text{'}$ 表示没有门道。 - $c_{1,2j} = c_{2h+1,2j} = \text{'}-\text{'}$ ($1 \leq j \leq w$) 和 $c_{2i,1} = c_{2i,2w+1} = \text{'}|\text{'}$ ($1 \leq i \leq h$)，对应地牢的外墙。 - $c_{2i+1,2j+1} = \text{'}+\text{'}$ 对于 $0 \leq i \leq h$ 和 $0 \leq j \leq w$，对应墙壁或外墙的交点。 地牢的入口和出口分别位于房间 $(1,1)$ 和 $(h,w)$。配置满足上述的树状属性。

输出通过改造可以达到的从入口房间到出口房间的路径的最大长度，其中路径长度是经过的房间数量，包括入口和出口房间。

在第一个样例中，如果你封闭房间 $(1,1)$ 和 $(1,2)$ 之间的门道，并在房间 $(2,1)$ 和 $(2,2)$ 之间建造一个新的门道，那么从 $(1,1)$ 到 $(2,3)$ 的唯一路径将经过全部 $6$ 个房间，这显然是最大值。 在第二个样例中，任何改造都将使得从 $(1,1)$ 到 $(2,3)$ 的唯一路径长度保持恰好为 $4$。 在第三个样例中，一种最优方式是封闭房间 $(4,2)$ 和 $(4,3)$ 之间的门道，并在房间 $(2,4)$ 和 $(3,4)$ 之间建造一个新的门道。 上述改造后的配置如下所示。 ``` +-+-+-+ +-+-+-+ +-+-+-+-+-+ |.|...| |...|.| |...|...|.| +.+.+.+ +.+.+.+ +-+.+.+.+.+ |...|.| |.|...| |...|.|.|.| +-+-+-+ +-+-+-+ +.+.+.+.+.+ |.|...|.|.| +.+.+-+.+.+ |.|.|...|.| +-+.+.+-+.+ |...|.....| +-+-+-+-+-+ ```