T345262 网格图 - 逃出城堡castle.cpp

小 Biu 被困在一个城堡中，城堡可以看成一个大小为 n×n 的二维平面上的网格图，每一个格子要么为平地，要么为墙壁，要么为毒区，而且作为毒区的格子，每一秒会向他周围的上下左右四个格子扩散毒气(毒气不能穿过墙壁)。现在小 Biu 身负重任，最开始小 Biu 在某一个平地上，他每一秒可以向他上下左右四个格子中的作为平地的格子移动一步，他想知道如果不能穿越墙壁，也不能接触有毒气的格子(如果毒气和小 Biu 同时到达某个平地，也算接触)，他最少需要多长时间才能逃出城堡，只要从任何一个边缘走出城堡都算逃出城堡。  如图所示的数据中，只要小 Biu 先向右移动两步，再向下移动两步，即可逃出城，所以答案为 4 。 输入格式 第 1 行：一个整数 n ，表示城堡的大小是一个 n×n 的网格图。 (1≤n≤1000) 第 2−n+1 行：每一行有 n 个字符，'.'表示平地，'*'表示有毒气的格子，'#'表示墙壁，' s′(小写字母) 表示小 Biu 最开始的位置。 输出格式 输出一个整数表示答案，如果小 Biu 不能逃出城堡则输出"IMPOSSIBLE"( 不带引号)。 输入样例 5 .*... ....# .*..# #s..# .##.# 输出样例 4

无

无

无