【算法分析】 求最少需要多少步，考虑使用广搜。从起点开始进行搜索，规则只能向上下左右走动，当搜索到终点时就结束。 【参考代码】 【时间复杂度】 O(n∗m)O(n*m)O(n∗m) 【预计得分】 100pts100pts100pts

#include<iostream> #include<cstring> #include<queue> using namespace std; int n,m; //n行 m列 char a[45][45]; //a是地图 int vis[45][45]; //标记走了多少步 int dx[4]={1,0,-1,0}; //改变x坐标 int dy[4]={0,1,0,-1}; //改变x坐标 struct node{ //表示一个点(x,y) int x,y; }; void bfs(int x,int y){ memset(vis,-1,sizeof vis); //给vis数组全部初始化为-1 queue<node > que; //创建队列 que.push({x,y}); vis[x][y] = 0; while(que.size()){ node n1 = que.front(); //拿到队头数据 que.pop(); //出队 for(int i=0;i<4;i++){ int xx=n1.x+dx[i]; int yy=n1.y+dy[i]; if(xx>=0 && xx<n && yy>=0 && yy<m && a[xx][yy]!='#' && vis[xx][yy]==-1){ que.push({xx,yy}); vis[xx][yy] = vis[n1.x][n1.y]+1; } } } } int main(){ cin>>n>>m; for(int i=0;i<n;i++) cin>>a[i]; bfs(0,0); cout<<vis[n-1][m-1]+1; //加上起点 return 0; }

起点也是点。

1. 广搜： 2. 深搜（TLE)： 3.骗分：

1、Python 2、C++

#include<bits/stdc++.h> using namespace std; char mp[45][45]; int n,m; bool vis[45][45]; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; struct node{ int x,y,step; }r,l; void bfs(int x,int y,int step){ queue<node> q; q.push({x,y,step}); vis[x][y] = 1; while(q.size()){ r = q.front(); if(r.x == n&&r.y == m){ cout<<r.step; return; } q.pop(); for(int i=0;i<4;i++){ l.x = r.x + dx[i]; l.y = r.y + dy[i]; l.step = r.step + 1; if(l.x>=1&&l.x<=n&&l.y>=1&&l.y<=m&&mp[l.x][l.y]!='#'&&vis[l.x][l.y]==0){ vis[l.x][l.y] = 1; q.push(l); } } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mp[i][j]; } } bfs(1,1,1); }

双向广搜： 顾名思义，就是一边从头搜，一边从尾搜 它可以减少时间复杂度，但有几率增加空间复杂度 先初始化和输入 （这步不用教吧） 接下来，由于要两边一起来，所以要弄2个队列（q1,q2)和2个标记数组(v1,v2（在上面）) 然后就是本解法的华点： 当两边有一端无路可走时，就结束了 然后，优先解决队列中较多的那一头 剩下的就和正常广搜一样了 最后，献上完整代码，请勿直接搬运，抄袭可耻

十分感谢@注释对本题解的贡献

正确题解

#include<iostream> #include<queue> using namespace std; const int N = 45; int dx[4]={-1,1,0,0};//上下左右 int dy[4]={0,0,-1,1}; char mp[N][N]; bool vis[N][N]; int n,m;//行 列 //结构体存点信息 struct node { int x,y,step; }r,l;//r是代表当前点，l是代表下一点 //开始广搜 void bfs(int x,int y,int step){ //定义一个队列（结构体） queue<node> q; //①将起点放入队列，并标记为已访问 q.push({x,y,step}); vis[x][y]=1; //在队列还有元素的情况下，重复二、三步 while(q.size()){ // 等同于while(!q.empty()) //②取出队首，作为当前点，不要忘记弹出一个空间 r=q.front(); q.pop(); //判断队首是不是目标节点 if(r.xn&&r.ym){ cout<<r.step;//是，就输出 return; } //③找当前点的邻居，看是否符合要求，是的话就入队 for(int i=0;i<4;i++){ l.x = r.x + dx[i];//下一点信息 l.y = r.y + dy[i]; l.step = r.step + 1;//步数也加一 //要求：在界内 不是障碍 没有被走过 if(l.x>=1 && l.x<=n && l.y>=1 && l.y<=m && mp[l.x][l.y]!='#' && vis[l.x][l.y]==0){ vis[l.x][l.y] = 1;//标记下一个点可以走 q.push(l);// l入队 } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mp[i][j];//输入地图信息 } } bfs(1,1,1);//广搜，传入起点坐标（1，1）和初始步数 1 }

#include <bits/stdc++.h> using namespace std; char mp[45][45]; bool vis[45][45]; struct node{ }l,r; int n,m; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int main(){ }

啊吧啊吧 看注释吧，广搜写法