深度优先搜索
深度优先搜索即遍历枚举每一种情况，可以用栈进行储存或者递归，这边暂时只会递归；
#include<bits/stdc++.h> using namespace std; const int N=1e2+10; int mp[N][N],vis[N][N]; bool fg=false; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int n; int sx,sy,ex,ey; // bool check(int nx,int ny){ // if(nx>0&&nx<n&&ny>0&&ny<=n&&vis[nx][ny]!=false&&mp[nx][ny]==0){ // return true; // } // return false; // } void dfs(int x,int y){ if(vis[x][y]||fg)return; vis[x][y]=true; if(x==ex&&y==ey){ fg=true; return; } for(int i=0;i<4;++i){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx>0&&nx<=n&&ny>0&&ny<=n&&vis[nx][ny]==false&&mp[nx][ny]==0){ dfs(nx,ny); } } } int main(){ cin>>n; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ cin>>mp[i][j]; } } cin>>sx>>sy>>ex>>ey; if(mp[sx][sy]==1){ puts("NO"); return 0; } dfs(sx,sy); puts(fg?"YES":"NO"); return 0; }
广度优先搜索
广度优先搜索需要先学习一下队列
这个代码不知道哪里错了
#include<bits/stdc++.h> using namespace std; const int N=1e2+10; char mp[N][N]; int vis[N][N]; bool fg=false; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int n,m; struct Edge{ int x,y,w; }; //int sx,sy,ex,ey; // bool check(int nx,int ny){ // if(nx>0&&nx<n&&ny>0&&ny<=n&&vis[nx][ny]!=false&&mp[nx][ny]==0){ // return true; // } // return false; // } bool check(int nx,int ny){ if(nx>0&&nx<n&&ny>0&&ny<=m&&vis[nx][ny]!=false/*可加可不加*/&&mp[nx][ny]=='.'){ return true; } return false; } int bfs(){ queue<Edge>que; que.push({1,1,0}); vis[1][1]=true; while(!que.empty()){ Edge p=que.front(); que.pop(); if(p.x==n&&p.y==n){ return p.w+1; } if(vis[p.x][p.y])continue; vis[p.x][p.y]=true; for(int i=0;i<4;i++){ int nx=p.x+dx[i]; int ny=p.y+dy[i]; if(check(nx,ny)){ que.push({nx,ny,p.w+1}); } } } } int main(){ cin>>n>>m; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ cin>>mp[i][j]; } } cout<<bfs()<<endl; //cin>>sx>>sy>>ex>>ey; // if(mp[sx][sy]==1){ // puts("NO"); // return 0; // } // bfs(); // puts(fg?"YES":"NO"); return 0; }
下面是正确的代码
#include<iostream> #include <queue> using namespace std; int judge[41][41]={0};//标记地图 char a[41][41];//地图 int r,c; struct node{ int x; int y; int step; node(int xx,int yy,int stepp){ x=xx; y=yy; step=stepp; } };//便于存储，可以直接node a（0，0，0）初始化，即a.x=0。。。。。 int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};//改变方向 queue<node> q;//设置队列 bool check(int x,int y){//判断是否符合条件 if(x<0||x>=r||y<0||y>=c||judge[x][y]||a[x][y]=='#'){ return false; } return true; }; int bfs(node start){ node next(0,0,0),cur(0,0,0); while(!q.empty()){//如果q空还没有找到，那就是找不到了 cur=q.front(); q.pop(); if(cur.x==r-1&&cur.y==c-1){//终止条件，即找到终点了 return cur.step+1; } for(int i=0;i<4;i++){ next.x=cur.x+dir[i][0];//横坐标变换 next.y=cur.y+dir[i][1];//纵坐标变换 next.step=cur.step+1;//每次遍历周围的一个点，就走一步，如果不符合下面if里面的条件，此时的next也不会被push进q里面，相当于回溯 if(check(next.x, next.y)){ q.push(next); judge[next.x][next.y]=1;//标记已走过 } } } return -1; } int main(){ cin>>r>>c; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ cin>>a[i][j]; } } node start(0,0,0); q.push(start); judge[0][0]=1; cout<<bfs(start)<<endl; return 0; }
