吐槽
这搜索，真TMD恶心。我调了俩小时。。。。。。丧尽天良
坑点
从出口往里跳的时候只能挑一格。从别的格子跳往其他格子的时候只能跳两格跳两格的时候还必须判断中间隔过去的一格是不是空格输入格式也很恶心，在要求读空格的前提下好的办法只有gets，但是用gets会把两个整数后面的回车读进去。。
思路
从数据范围来看的话，从每个点都搜一遍最短距离是不现实的了。。当然不排除你写的很好看QwQ。我的想法是将两个出口找出来，然后跑两边BFS，每个点都维护一个距离的最小值
要注意分类讨论从出口往别的格子跳和从普通格子跳往普通格子。跑的还挺快。空间也不大。我排在最优解的第二页QwQ
代码
#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);
}
转载于:https://www.cnblogs.com/bljfy/p/9309688.html
