UVA1253 Infected Land

地球正受到致命病毒的攻击。幸运的是，卫生部的及时行动针对这种紧急情况，成功地将感染的传播限制在一个正方形的网格区域内。最近，公共卫生专家发现了一个关于感染者转变的有趣模式区域。在时间的每一步，网格中的每个区域都会根据感染情况改变其感染状态其直接(水平、垂直和对角)相邻区域的状态。 - 如果一个感染区域有两个或三个相邻的感染区域，它就会继续被感染。 - 如果一个未感染区域恰好有三个相邻的感染区域，则该区域被感染。 - 否则，某个区域将没有病毒。 你的任务是对抗病毒并对**所有区域**进行消毒。卫生部让一个你指挥的反病毒车辆原型。车辆的功能总结如下： - 在每个时间步开始时，你将车辆移动到八个相邻区域之一。这不允许车辆移动到受感染区域(以保护操作人员免受病毒感染)。不允许呆在同一个地方。 - 随着车辆运动，除了车辆所在区域之外的所有区域都将改变它们的感染状态根据上述转换规则。 车辆的特殊功能保护其区域免受病毒感染，即使该区域邻近精确到三个感染区域。不幸的是，车辆的这种病毒防护能力不是最后一个。一旦车辆离开该区域，根据邻近区域的感染状态，该区域可能被感染。车辆所在的未受感染区域对其邻近区域的影响与就过渡规则而言是一个受感染的区域。 下面的一系列图表展示了一个成功实现目标的示例场景。最初，你用@表示的车辆在(1，5)的5 × 5网格区域内被发现，你会看到一些由#表示的感染区域。  首先，在时间步骤1的开始，你把你的车斜向西南移动，也就是说，到区域(2，4)。请注意，这种车辆运动是可能的，因为该区域在时间开始步骤1。 随着该车辆运动，每个区域的感染状态根据过渡规则而改变。图中的“1-end”列说明了在时间步骤1结束时这种变化的结果。注意区域(3，3)被感染是因为有两个相邻的**感染区域和载体也在邻近地区**，总共三个地区。 在时间步骤2中，您将车辆移至西方，并将其放置在(2，3)处。然后其他区域的感染状态发生变化。请注意，即使您的车辆恰好有三名感染者邻近区域(西部、西南部和南部)，车辆正在访问的区域**未被感染**。在时间步骤2结束时，这种变化的结果如“2-end”中所示。 最后，在时间步骤3，你把你的车移到东边。感染状态改变后，你看到所有的区域都没有病毒了！这种彻底消毒的情况是我们的目标。在我们看到的场景中，您已经在三个时间步骤中成功地对所有区域进行了消毒命令车辆移动(1)西南，(2)西，(3)东。你的任务是找到最短的车辆运动命令序列的长度成功消毒所有区域。

输入是一系列数据集。输入的结束由包含单个零。每个数据集的格式如下。  安这里，n是网格的大小。这意味着网格由n × n个区域组成。你可以假设1 ≤ n ≤ 5。数据集的其余部分由n行n个字母组成。每个字母aij指定开头区域的状态:“#”表示感染，“.”表示没有病毒，初始位置为“@” 车辆的。行中唯一可以出现的字符是“#”、“.”、或“@”。在n × n区域中，有恰好存在一个包含“@”的区域。

对于每个数据集，输出消毒所有区域所需的最小时间步数。如果不存在导致完全消毒的运动命令序列，输出'-1 '。输出不应包含任何其他额外字符。 ## 样例输入 ~~~ 3 ... .@. ... 3 .## .#. @## 3 ##. #.. @.. 5 ....@ ##... #.... ...#. ##.## 5 #...# ...#. #.... ...## ..@.. 5 #.... ..... ..... ..... ..@.. 5 #..#. #.#.# .#.#. ....# .#@## 5 ..##. ..#.. #.... #.... .#@.. 0 ~~~ ## 样例输出 ~~~ 0 10 -1 3 2 1 6 4 ~~~