题解 P1519 【穿越栅栏 Overfencing】
题目大意
按照字符画的形式给定一个地图，这个地图有两个出口，现在你需要求出从所有的点到任意一个出口的距离中的最短路径的最大值
吐槽大会
这道搜索题，真恶心。我调了俩小时。。。。。。丧尽天良
解题思路
从数据范围来看的话，从每个点都搜一遍最短距离是不现实的了。
当然不排除你写的很好看QwQ。
我的想法是将两个出口找出来，然后跑两边BFS，每个点都维护一个距离的最小值
要注意分类讨论从出口往别的格子跳和从普通格子跳往普通格子。
跑的还挺快，空间消耗也不大。我排在最优解的第二页QwQ
巨坑所在
你以为这样就完了吗，你就能轻易AC吗？
显然是不能的，这个题还有四个不易发现的坑点，要不我怎么会调那么久呢？
-
从出口往里跳的时候只能挑一格。
-
从别的格子跳往其他格子的时候只能跳两格
-
跳两格的时候还必须判断中间隔过去的一格是不是空格
-
输入格式也很恶心，在要求读空格的前提下好的办法只有gets，但是用gets会把两个整数后面的回车读进去。
附上代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
const int INF = 2147483647;
using namespace std;
int n, m, sx[3], sy[3], cnt, ans;
char map[208][90];
int dis[208][90];
int dx[5] = {0, 2, 0, -2};
int dy[5] = {2, 0, -2, 0};
int rx[5] = {0, 1, 0, -1};
int ry[5] = {1, 0, -1, 0};
struct node {
int x, y, sum;
}temp, now;
queue<node> Q;
bool vis[208][90];
inline void BFS(int num) {
memset(vis, 0, sizeof(vis));
while (!Q.empty()) Q.pop();
vis[sx[num]][sy[num]] = 1;
temp.sum = 0, temp.x = sx[num], temp.y = sy[num];
Q.push(temp);
while (!Q.empty()) {
now = Q.front();
int x = now.x, y = now.y, s = now.sum;
Q.pop();
dis[x][y] = min(s, dis[x][y]);
for(int i=0; i<4; i++) {
int xx = dx[i]+x, yy = dy[i]+y;
int zx = rx[i]+x, zy = ry[i]+y;
if(!vis[xx][yy] && map[xx][yy] == ' ' && xx <= 2*n+1 && xx > 0 && yy <= 2*m+1 && yy > 0 && map[zx][zy] == ' ' && (x != sx[num] || y != sy[num])) {
vis[xx][yy] = 1;
temp.x = xx, temp.y = yy, temp.sum = s+1;
Q.push(temp);
}
if(!vis[zx][zy] && map[zx][zy] == ' ' && x == sx[num] && y == sy[num] && zx <= 2*n+1 && zy <= 2*m+1 && zx > 0 && zy > 0) {
vis[zx][zy] = 1;
temp.x = zx, temp.y = zy, temp.sum = s+1;
Q.push(temp);
}
}
}
}
int main() {
scanf("%d%d", &m, &n);
for(int i=1; i<=2*n+1; i++) {
for(int j=1; j<=2*m+1; j++) {
dis[i][j] = INF;
}
}
gets(map[0]);
for(int i=1; i<=2*n+1; i++) {
gets(map[i]+1);
for(int j=1; j<=2*m+1; j++) {
if(i == 1 || j == 1 || i == 2*n+1 || j == 2*m+1)
if(map[i][j] == ' ') {
sx[++cnt] = i;
sy[cnt] = j;
}
}
}
BFS(1);
BFS(2);
for(int i=1; i<=2*n+1; i++) {
for(int j=1; j<=2*m+1; j++) {
if(dis[i][j] != INF)
ans = max(ans, dis[i][j]);
}
}
printf("%d", ans);
}管理大大求求您给我个通过吧