BFS＆DFS遍历

深度和广度优先遍历

–``比如迷宫题目

https://www.acwing.com/problem/content/description/1115/

DFS代码为

#include <iostream>
#include <queue>

using namespace std;
const int N = 25;

struct node
{
    
    int x;
    int y;
};

int n,m;
int result1=0;
char g[N][N];
void dfs(int x,int y){
    
    int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

    g[x][y]='#';
    for(int i=0;i<4;i++){
    
        int a= x+dx[i],b=y+dy[i];
        if(a>=0 && a<n && b>=0 && b<m && g[a][b]=='.'){
    
            result1++;
      
            dfs(a,b);
        }
    }
}
int main(){
    
    while(cin>>m>>n,n||m){
    
        result1=0;
        int x,y;
        for(int i=0; i<n;i++)cin>>g[i];
        for(int i=0; i<n; i++ )
            for(int j=0;j<m;j++){
    
                if(g[i][j]=='@'){
    
                    x=i;
                    y=j;
                }
            }
        dfs(x,y);
        cout<<result1+1<<endl;
    }
 
}

BFS代码为

#include <iostream>
#include <queue>

using namespace std;
const int N = 25;
struct node
{
    
    int x;
    int y;
};

int n,m;
char g[N][N];
int bfs(int x,int y){
    
    int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};
    int res=0;
    node N1,N2;
    N1.x=x;
    N1.y=y;
    g[x][y]='#';
    queue<node> q;
    q.push(N1);
    
    while (q.size()){
    
        auto t = q.front();
        res++;
        q.pop();
        for(int i=0;i<4;i++){
    
            int Nx = t.x+dx[i];
            int Ny = t.y+dy[i];
            if(Nx >= 0 && Nx < n && Ny<m && Ny >= 0 && g[Nx][Ny]=='.'){
    
            N2.x= Nx;
            N2.y= Ny;
            g[Nx][Ny]='#';
            q.push(N2);
            }
        }
    }
    return res;
}
int main(){
    
    while(cin>>m>>n,n||m){
    
        int x,y;
        for(int i=0; i<n;i++)cin>>g[i];
        for(int i=0; i<n; i++ )
            for(int j=0;j<m;j++){
    
                if(g[i][j]=='@'){
    
                    x=i;
                    y=j;
                }
            }
        cout<<bfs(x,y)<<endl;
    }
 
}