广度优先搜索BFS

关于42号星球 / 2023-07-04 / 原文

广度优先搜索BFS

必须学习过队列、结构体（pair）才能够学广度优先搜索

B3625 迷宫寻路

可以让学生用深搜做一遍，复习一下深搜

然后讲广搜

 1 //深搜 60分 
 2 #include<iostream>
 3 #include<queue>
 4 using namespace std;
 5 int n,m,flag;
 6 char a[110][110];
 7 int dx[5]= {0,-1,0,1,0};
 8 int dy[5]= {0,0,1,0,-1};
 9 void dfs(int x,int y) {
10     if(flag) return;
11     if(x==n&&y==m) {
12         flag=1;
13         return;
14     }
15     for(int i=1; i<=4; i++) {
16         int nx=x+dx[i];
17         int ny=y+dy[i];
18         if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]=='.') {
19             a[nx][ny]='#';
20             dfs(nx,ny);
21             a[nx][ny]='.';
22         }
23     }
24     return;
25 }
26 int main() {
27     cin>>n>>m;
28     for(int i=1; i<=n; i++) {
29         for(int j=1; j<=m; j++) {
30             cin>>a[i][j];
31         }
32     }
33     dfs(1,1);
34     if(flag) cout<<"Yes"<<endl;
35     else cout<<"No"<<endl;
36     return 0;
37 }

 1 //广搜 100分
 2 #include<iostream>
 3 #include<queue>
 4 #include<utility>
 5 using namespace std;
 6 typedef pair<int,int> pii;
 7 pii a,b;
 8 int n,m,flag;
 9 char c[110][110];
10 int dx[5]= {0,-1,0,1,0};
11 int dy[5]= {0,0,1,0,-1};
12 void bfs(int x,int y) {
13     queue<pii> q;
14     a.first=x;
15     a.second=y;
16     q.push(a);
17     while(!q.empty()) {
18         a=q.front();
19         q.pop();
20         for(int i=1; i<=4; i++) {
21             int nx=a.first+dx[i];
22             int ny=a.second+dy[i];
23             if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&c[nx][ny]=='.') {
24                 b.first=nx;
25                 b.second=ny;
26                 if(nx==n&&ny==m) {
27                     flag=1;
28                     return;
29                 }
30                 q.push(b);
31                 c[nx][ny]='#';
32             }
33         }
34     }
35     return;
36 }
37 int main() {
38     cin>>n>>m;
39     for(int i=1; i<=n; i++) {
40         for(int j=1; j<=m; j++) {
41             cin>>c[i][j];
42         }
43     }
44     bfs(1,1);
45     if(flag) cout<<"Yes"<<endl;
46     else cout<<"No"<<endl;
47     return 0;
48 }

P1443 马的遍历

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
pii a,b;
int n,m,flag;
int c[410][410];
int dx[8]= {-1,-2,-2,-1,1,2,2,1};
int dy[8]= {2,1,-1,-2,2,1,-1,-2}; //8个方向
void bfs(int x,int y) {
    queue<pii> q;
    a.first=x;
    a.second=y;
    q.push(a);
    while(!q.empty()) {
        a=q.front();
        q.pop();
        for(int i=0; i<8; i++) {
            int nx=a.first+dx[i];
            int ny=a.second+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&c[nx][ny]==-1) {
                b.first=nx;
                b.second=ny;
                q.push(b);
                c[nx][ny]=c[a.first][a.second]+1;
            }
        }
    }
    return;
}
int main() {
    int x,y;
    cin>>n>>m>>x>>y;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            c[i][j]=-1;
        }
    }
    c[x][y]=0;
    bfs(x,y);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            printf("%5d",c[i][j]);
        }
        cout<<endl;
    }
    return 0;
}