Problem 82: Overfencing
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; 2*H+1 lines with width 2*W+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 2*H+2: |
2*W+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. 题意:给出的迷宫有两个出口,求出迷宫内任意点到出口的最短距离。要求输出的是所有最短距离中的最大值。代码如下:
/*
LANG: C
TASK: maze1
*/
#include<stdio.h>
#define Max(a, b) ( a > b ? a : b)
#define Min(a, b) ( a < b ? a : b)
int end[2][2], M[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
char s[210][100];//迷宫地图
int t[210][100], queue[20000][2], max = 0, dis[2][210][100];//dis用来存取点到两个出口的距离,t用于标记是否visit过
void Set(int n, int m, int h)
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
dis[h][i][j] = -1;
t[i][j] = 0;
}
}
}
void Bfs(int x, int y, int n, int m, int h)
{
int start = 0, end = 0, i, row, col;
queue[start][0] = x;
queue[start][1] = y;
dis[h][x][y] = 1;
t[x][y] = 1;
end++;
while (start != end)
{
x = queue[start][0], y = queue[start][1];
for (i = 0; i < 4; i++)
{
row = x + M[i][0], col = y + M[i][1];
if (row >= 0 && row < n && col >= 0 && col < m && !t[row][col] && s[row][col] == ' ')
{
queue[end][0] = row, queue[end][1] = col, dis[h][row][col] = dis[h][x][y] + 1, t[row][col] = 1;
end++;
}
}
start++;
}
}
int main()
{
freopen("maze1.in", "r", stdin);
freopen("maze1.out", "w", stdout);
int n, m, i, j, k;
scanf("%d%d", &n, &m);
getchar();
n = n * 2 + 1;
m = m * 2 + 1;
k = 0;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
scanf("%c", &s[i][j]);
if (s[i][j] == ' ' && (i == 0 || i == m - 1 || j == 0 || j == n - 1))
{
end[k][0] = i, end[k++][1] = j;
}
}
getchar();
s[i][j] = 0;
}
Set(m, n, 0);
Bfs(end[0][0], end[0][1], m, n, 0);
Set(m, n, 1);
Bfs(end[1][0], end[1][1], m, n, 1);
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (dis[0][i][j] != -1)
{
max = Max(max, Min(dis[0][i][j], dis[1][i][j]));
}
}
}
printf("%d\n", max / 2);//最后距离要除2,不知道为什么
fclose(stdin);
fclose(stdout);
//system("pause");
return 0;
}