题目解析
阅读完题目可知题目要求的是:从起点(1,1)到终点(r,c)的最短路。且在迷宫中,可视为边权为1,也就是一个单源的无权最短路问题。那么我们可以采用BFS来解决这个问题。
BFS求最短路框架
void bfs(int sx,int sy){//从(sx,sy)出发
queue<node> q;
q.push(node{sx,sy});//起点入队
vis[sx][sy]=1;//标记起点
ans[sx][sy]=1;//记录起点的最短步数
while(!q.empty()){//循环直到队列为空
node cur=q.front();
q.pop();
for(int i=L;i<R;i++){//遍历邻接点
int nx=cur.x+dx[i],ny=cur.y+dy[i];//计算下一步位置
if(!check(nx,ny)) continue;//不能到达的位置跳过
vis[nx][ny]=1;
ans[nx][ny]=ans[cur.x][cur.y]+1;//更新最短路
q.push(node{nx,ny});
}
}
}
需要注意本题的行走方式,在*
不能行走,+
上下左右都可以,-
只能左右,|
只能上下。那么我们需要根据不同情况处理不同的行走方式。并且注意起点部分为的最短路为1.
完整代码
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,y;
};
int r,c;
char a[25][25];
int ans[25][25];
bool vis[25][25];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
void bfs(int sx,int sy){//从(sx,sy)出发
queue<node> q;
q.push(node{sx,sy});
vis[sx][sy]=1;//起点入队
ans[sx][sy]=1;//记录起点的最短步数
while(!q.empty()){//循环直到队列为空
node cur=q.front();
q.pop();
int L=0,R=0;
if(a[cur.x][cur.y]=='+'){
L=0;R=4;
}else if(a[cur.x][cur.y]=='-'){
L=2;R=4;
}else if(a[cur.x][cur.y]=='|'){
L=0;R=2;
}
for(int i=L;i<R;i++){//遍历邻接点
int nx=cur.x+dx[i],ny=cur.y+dy[i];//计算下一步位置
//不能到达的位置跳过
if(nx<1||nx>r||ny<1||ny>c) continue;
if(vis[nx][ny]||a[nx][ny]=='*') continue;
vis[nx][ny]=1;
ans[nx][ny]=ans[cur.x][cur.y]+1;//更新最短路
q.push(node{nx,ny});
}
}
}
int main(){
int t;
cin>>t;
while(t--){
//注意多组数据清空
memset(ans,-1,sizeof(ans));
memset(vis,0,sizeof(vis));
memset(a,0,sizeof(a));
cin>>r>>c;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
cin>>a[i][j];
}
}
bfs(1,1);
cout<<ans[r][c]<<endl;
}
return 0;
}
1 条评论
博主真是太厉害了!!!