题解 | #牛牛走迷宫#
牛牛走迷宫
https://ac.nowcoder.com/acm/problem/21583
用bfs肯定没有问题，但就是处理 t + 1和 t + 2,可能第一会想到结构体加优先队列，但这种思路不对，可能会出现下面这种情况
. # # # # # # 步数是 0 # # # # # #
. . . . . . . 1 2 3 4 5 6 7
# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # . # # # # # # 9
# # # # . # # # # # # 7 # #
# # # # . . . # # # # 8 9 .对于这最后一个点他上一步可以是上面那个9跳两步过来的时间为11；也可能是右边走过来的10
问题就在于优先队列对于时间相同是无法处理的，这和自己设置的dx和dy的先往哪个方向移动有关
也可能是###9
#9#.
所以无法通过dx，dy来确定最后一次是移动还是跳跃，故在优先队列的基础上加上移动到这一步的总的时间是不是能被更小的值更新，即如果出现时间更短的时候再让这个值重新入队，所以和优先队列没有关系。不需要时间短先用，时间短的也可能被时间长的更新，只需要dist[a][b]== -1 || t+1<dist[a][b]如果这个成立就更新入队
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char g[100][100];
int dist[100][100];
int r1,c1,r2,c2,n,m;
struct nod
{
int w,x,y;
};
bool check(int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<m)
return 1;
return 0;
}
void bfs()
{
memset(dist,-1,sizeof dist);
queue<nod>q;
q.push({0,r1,c1});
dist[r1][c1]=0;
while(q.size())
{
auto [t,x,y]=q.front();q.pop();
//不能在这里输出dist[a][b],因为可能会更新他
for(int i=0;i<4;i++)
{
int a = x+dx[i],b=y+dy[i];
if(g[a][b]=='.')
{
if(check(a,b)&&(dist[a][b]==-1||t+1<dist[a][b]))
//这里一定要t+1<dist[a][b]，因为如果跳过去之前和走过去之前
//时间是一样的，但挑过去在队头，那时间就变成t+2,但其实是t+1
{
dist[a][b] = t+1;
q.push({t+1,a,b});
}
}
else
{
while(g[a][b]=='#'&&check(a,b))
{
a+=dx[i],b+=dy[i];
}
if(check(a,b)&&(dist[a][b]==-1||t+1<dist[a][b]))
{
dist[a][b]=t+2;
q.push({t+2,a,b});
}
}
}
}
cout<<dist[r2][c2]<<endl;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
cin>>g[i];
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
bfs();
return 0;
}
查看30道真题和解析