题目描述

推箱子游戏在一个 $N \times N$ 的矩形迷宫中进行，每个单元格要么为空（用 '.' 字符表示，ASCII 码为 46），要么被墙壁占据（用 '#' 字符表示，ASCII 码为 35）。此外，还有一个单独的目标单元格，用 '*' 字符表示（ASCII 码为 42）。

一名玩家和一个箱子位于迷宫的空单元格中。玩家可以在空单元格之间沿水平或垂直方向移动。如果玩家试图移动到的单元格被箱子占据，箱子会被“推”到同一方向的下一个单元格。当然，下一个单元格必须为空。

游戏的目标众所周知：用最少的移动步数将箱子放置到目标单元格。然而，你的任务不同：给定游戏场地，选择玩家和箱子的起始位置，以使所需的移动步数最大化。

输入

输入的第一行包含数字 $N$，即场地的大小。接下来的 $N$ 行，每行包含 $N$ 个字符，表示游戏场地。输入的场地中始终至少有一个与目标单元格相邻的空单元格。

$2 \leq N \leq 25$

输出

输出必须包含一个整数，即最大移动步数。

3
..#
...
..*

10

来源

2004 年欧洲东北部，远东分区