题目

题解

类型

很经典的BFS模板题，最短路径大多数采用BFS解决，但是BFS的缺点是空间复杂度太大，我们必须进行剪枝操作，即标记自己已经走过的点，而且一定要注意，在入队push操作之后就可以标记自己已经走过的点了，否则后面一定会有重复的位置进入队列，从而造成内存超限。

内存超限版本

#include<iostream>
#include<queue>using namespace std;struct Node
{int _x,_y;int _cnt;Node(){};Node(int x,int y,int cnt):_x(x),_y(y),_cnt(cnt){};
};const int INF=100000;
int n,m;
char f[110][110];
int bx=0,by=0;
// queue<Node>q;int bfs();int main(){cin >> n >> m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin >> f[i][j];if(f[i][j]=='S'){// q.push(Node(i,j,0));bx=i;by=j;}}}int res=bfs();if(res==INF){cout << "没有出路！" << endl;}else{cout << res << endl;}// system("pause");return 0;
}int bfs(){queue<Node>q;q.push(Node(bx,by,0));int move[4][2]={{0,1},{0,-1},{1,0},{-1,0}};while(!q.empty()){//队列不为空，继续BFS        //BFS要不要标记走过的路？当然//在什么时候标记？在走到的时候就标记int x,y,cnt;Node node=q.front();q.pop();x=node._x;y=node._y;cnt=node._cnt;//退出条件if(f[x][y]=='G'){return node._cnt;}//标记自己走过的路f[x][y]='#';//四个方向搜索for(int ix=0;ix<4;ix++){int nx,ny;nx=x+move[ix][0];ny=y+move[ix][1];//移动完成，开始判断if(0<=nx&&nx<n&&0<=ny&&ny<m&&f[nx][ny]!='#'){//次数++//放入队列q.push(Node(nx,ny,cnt+1));}}}return INF;
}

我们可以看到在q.push()之后，笔者并没有标记当前点已经走过，而是选择等到这一点从队列里出来的时候被检测到了才将这一点标记成#，所以内存超限了。

测试版

会输出循环次数和队列中的元素数量

#include<iostream>
#include<queue>using namespace std;struct Node
{int _x,_y;int _cnt;Node(){};Node(int x,int y,int cnt):_x(x),_y(y),_cnt(cnt){};
};const int INF=100000;
int n,m;
char f[110][110];
int bx=0,by=0;
int xunhuan=0;
int gx,gy;
// queue<Node>q;int bfs();int main(){cin >> n >> m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin >> f[i][j];if(f[i][j]=='S'){// q.push(Node(i,j,0));bx=i;by=j;}else if(f[i][j]=='G'){gx=i;gy=j;}}}int res=bfs();if(res==INF){cout << "没有出路！" << endl;}else{cout << res << endl;}cout << xunhuan <<endl;system("pause");return 0;
}int bfs(){queue<Node>q;q.push(Node(bx,by,0));f[bx][by]='#';int move[4][2]={{0,1},{0,-1},{1,0},{-1,0}};while(!q.empty()){//队列不为空，继续BFS        //BFS要不要标记走过的路？当然//在什么时候标记？在走到的时候就标记xunhuan++;cout << q.size() << endl;int x,y,cnt;Node node=q.front();q.pop();x=node._x;y=node._y;cnt=node._cnt;//退出条件if(x==gx&&y==gy){return node._cnt;}//四个方向搜索for(int ix=0;ix<4;ix++){int nx,ny;nx=x+move[ix][0];ny=y+move[ix][1];//移动完成，开始判断if(0<=nx&&nx<n&&0<=ny&&ny<m&&f[nx][ny]!='#'){//次数++//放入队列q.push(Node(nx,ny,cnt+1));//!赶紧在这里标记这个点已经走过了，不然后期入队的元素会有好多好多//!但是这里标记之后，我们会丧失终点G，因为G在被检查之前就被赋成了#//!所以我们要记录终点的坐标，通过坐标的判定，这样才能找到终点//标记自己走过的路f[nx][ny]='#';}}}return INF;
}

重点看注释，一定要在入队之后立马标记该点，不然队列里面的元素一定会重复。其实这里我们可以用一个set来判重，可以，但是没必要，有兴趣的可以自己去实现一下，在评论区告诉笔者

采用数组记录次数版

#include<iostream>
#include<queue>
using namespace std;const int INF=100000000;
typedef pair<int,int> P;char maze[105][105];
int N,M;
int sx,sy;
int gx,gy;int xunhuan=0;int d[105][105];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};int bfs(){queue<P> que;for(int i=0;i<N;i++){for(int j=0;j<M;j++){d[i][j]=INF;}}que.push(P(sx,sy));d[sx][sy]=0;while(que.size()){xunhuan++;cout<< que.size() << endl;P p=que.front();que.pop();if(p.first==gx&&p.second==gy){break;}for(int i=0;i<4;i++){int nx=p.first+dx[i];int ny=p.second+dy[i];if( 0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny]==INF){//这里相当于标记了已经走过的点que.push(P(nx,ny));d[nx][ny]=d[p.first][p.second]+1;//在这里标记这一点已经走过了//会在这里进行一个剪枝的操作，相当于标记进入队列的点已经走过了//这就意味着放在队列里的位置是不会在后面被检查的，这样就很舒服了，可以有效减少入队的数量}}}return d[gx][gy];
}
int main(){cin >> N >>M;for(int i=0;i<N;i++){for(int j=0;j<M;j++){cin >> maze[i][j];if(maze[i][j]=='S'){sx=i,sy=j;}else if(maze[i][j]=='G'){gx=i,gy=j;}}}cout << bfs() << endl;cout << xunhuan <<endl;system("pause");return 0;
}

类/结构体版本

#include<iostream>
#include<queue>using namespace std;//全局变量
class Node
{
public:int _cnt;int _x,_y;Node(){};Node(int x,int y,int cnt=0):_x(x),_y(y),_cnt(cnt){};
};int n,m;
char f[110][110];
int gx,gy;//记录终点终点坐标
queue<Node>q;
int mov[4][2]={{1,0},{-1,0},{0,1},{0,-1}};int bfs();int main(){cin >> n >>m;for(int i=0;i<n;++i){for(int j=0;j<m;++j){cin >> f[i][j];if(f[i][j]=='S'){q.push(Node(i,j));f[i][j]='#';}else if(f[i][j]=='G'){gx=i;gy=j;}}}int res=bfs();cout << res << endl;return 0;
}int bfs(){while(!q.empty()){//队列非空，开展检查Node node=q.front();    q.pop();int x,y;x=node._x;  y=node._y;if(x==gx&&y==gy){//检查是否是终点return node._cnt;}for(int i=0;i<4;i++){//四个方向int nx=x+mov[i][0];int ny=y+mov[i][1];if(0<=nx&&nx<n&&0<=ny&&ny<m&&f[nx][ny]!='#'){//判定是否越界或是墙q.push(Node(nx,ny,node._cnt+1));f[nx][ny]='#';}}}return 100000;
}

All In All

DFS易超时，BFS易超限，剪枝操作必不可少。

set判重版

这里提一嘴，由于我们的set用的是自定义类型，因此我们要自己写一个小于号重载，C++中set依靠红黑树实现（笔者也是道听途说，没有自己去确认过，各位谨慎），因此需要构造偏序关系。

#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;//全局变量
class Node
{friend int bfs();
private:int _cnt;int _x,_y;
public:Node(){};Node(int x,int y,int cnt=0):_x(x),_y(y),_cnt(cnt){};bool operator<(const Node&node)const{if(this->_x<node._x){return true;}else if(this->_x==node._x){return this->_y<node._y;}else{return false;}}};int n,m;
char f[110][110];
int gx,gy;//记录终点终点坐标
queue<Node>q;
int mov[4][2]={{1,0},{-1,0},{0,1},{0,-1}};int bfs();int main(){cin >> n >>m;for(int i=0;i<n;++i){for(int j=0;j<m;++j){cin >> f[i][j];if(f[i][j]=='S'){q.push(Node(i,j));f[i][j]='#';}else if(f[i][j]=='G'){gx=i;gy=j;}}}int res=bfs();cout << res << endl;return 0;
}int bfs(){set<Node>s;while(!q.empty()){//队列非空，开展检查Node node=q.front();    q.pop();int x,y;x=node._x;  y=node._y;if(x==gx&&y==gy){//检查是否是终点return node._cnt;}else{f[x][y]='#';}for(int i=0;i<4;i++){//四个方向int nx=x+mov[i][0];int ny=y+mov[i][1];if(0<=nx&&nx<n&&0<=ny&&ny<m&&f[nx][ny]!='#'){//判定是否越界或是墙Node n(nx,ny,node._cnt+1);if(s.find(n)==s.end()){q.push(n);s.insert(n);}}}}return 100000;
}

Over了，还是练得不够😢