10242 - 穿越栅栏
农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。 给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2H+1行，每行2W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数。（即使从这一点以最优的方 式走向最靠近的出口，它仍然需要最多的步数）当然了，牛们只会水平或垂直地在X或Y轴上移动，他们从来不走对角线。每移动到一个新的方格算作一步（包括移 出迷宫的那一步） 这是一个W=5,H=3的迷宫： +-+-+-+-+-+ | | +-+ +-+ + + | | | |
- +-+-+ + +
| | |
+-+ +-+-+-+ 如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。
输入
第一行： W和H（用空格隔开） 第二行至第2H+2行： 每行2W+1个字符表示迷宫
输出
输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。
样例
输入
5 3 +-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+
输出
9
提示
Overfencing Kolstad and Schrijvers Farmer John went crazy and created a huge maze of fences out in a field. Happily, he left out two fence segments on the edges, and thus created two "exits" for the maze. Even more happily, the maze he created by this overfencing experience is a `perfect' maze: you can find a way out of the maze from any point inside it.
Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2H+1 lines with width 2W+1 characters that represent the maze in a format like that shown later - then calculate the number of steps required to exit the maze from the worst' point in the maze (the point that is farther' from either exit even when walking optimally to the closest exit). Of course, cows walk only parallel or perpendicular to the x-y axes; they do not walk on a diagonal. Each move to a new square counts as a single unit of distance (including the move "out" of the maze.
Here's what one particular W=5, H=3 maze looks like:
+-+-+-+-+-+ | | +-+ +-+ + + | | | |
- +-+-+ + +
| | |
+-+ +-+-+-+
Fenceposts appear only in odd numbered rows and and odd numbered columns (as in the example). The format should be obvious and self explanatory. Each maze has exactly two blank walls on the outside for exiting.
PROGRAM NAME: maze1
INPUT FORMAT
Line 1: W and H, space separated
Lines 2 through 2H+2: 2W+1 characters that represent the maze
SAMPLE INPUT (file maze1.in) 5 3 +-+-+-+-+-+ | | +-+ +-+ + + | | | |
- +-+-+ + +
| | |
+-+ +-+-+-+
OUTPUT FORMAT A single integer on a single output line. The integer specifies the minimal number of steps that guarantee a cow can exit the maze from any possible point inside the maze. SAMPLE OUTPUT (file maze1.out) 9
The lower left-hand corner is nine steps from the closest exit.