当前位置 博文首页 > 文章内容

    1249 Lake Counting

    作者: 栏目:未分类 时间:2020-10-06 10:59:58

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    本题,我用了两种方法,个人认为DFS要更方便一点,至少从代码量来看是这样的

    #include<bits/stdc++.h>
    using namespace std;
    struct node{
        int x,y;
    }que[12110];
    int fx[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};//方向 
    char mp[120][120];//地图 
    int f,r;//队首队尾 
    int n,m;//行列 
    int ans;//水洼个数 
    
    void pr(){//测试函数 
        cout<<"---------"<<endl;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cout<<mp[i][j];
            }
            cout<<endl;
        }
    }
    
    void dfs(int x,int y){//DFS方法 
        for(int i=0;i<8;i++){
            int sx=x+fx[i][0];
            int sy=y+fx[i][1];
            
            if(sx>=0 && sx<n && sy>=0 && sy<m && mp[sx][sy]=='W'){
                mp[sx][sy]='.';
                dfs(sx,sy);
            }
        }
    }
    
    void bfs(int x,int y){//BFS方法 
        f=r=1;
        que[r].x=x , que[r].y=y , mp[x][y]='.';
        
        while(f<=r){
            node t;
            t.x=que[f].x , t.y=que[f].y;
            
            for(int i=0;i<8;i++){
                int nx=t.x+fx[i][0];
                int ny=t.y+fx[i][1];
                
                if(nx>=0 && nx<n && ny>=0 && ny<m && mp[nx][ny]=='W'){
                    mp[nx][ny]='.';
    //                pr();
                    r++;
                    que[r].x=nx;
                    que[r].y=ny;
                }
            }
            f++;
        }
    }
    int main(){
        cin>>n>>m;
        for(int i=0;i<n;i++)
            cin>>mp[i];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mp[i][j]=='W'){
                    ans++;
    //                dfs(i,j);
                    bfs(i,j);
                }
            }
        }
    //    pr();
        cout<<ans<<endl;
        return 0;
    }

     第65、66行,比较DFS与BFS