洛谷 P1596 [USACO10OCT] Lake Counting S 刷题条记

P1596 [USACO10OCT] Lake Counting S - 洛谷 | 计算机科学教诲新生态

一道判断有多少个联通块的问题
观察 对于水来说 其八个方向相邻都属于同一个联通块
我们可以存水的位置 搜刮每个水可以到达的所有位置 
将搜过的位置标记为陆地避免重复搜刮
搜完答案数+1
完整代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=110;
char a[N][N]={'.'};
bool b[N][N];
int c[N*N][2];
int dir[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int ans = 0;
void dfs(int x,int y){
        for(int i = 0;i < 8;i++)
        {
            int dx = x +dir[0];
            int dy = y +dir[1];//搜刮八个方向 
            if(a[dx][dy]=='W'&&dx>0&&dx<=n&&dy>0&&dy<=m)
            //假如下个位置为水且没有越界 
            {
                a[dx][dy] ='.';//标记为陆地 核心
                dfs(dx,dy);
            }
        }
}
int main(){
    cin>>n>>m;
    int maxx = max(n,m);
    for(int i = 0 ;i <= maxx;i++){
        /*b[0]   = true;
        b[0]   = true;
        b[n+1] = true;
        b[m+1] = true;*/
        a[0]   = '.';//将四条边界标记为陆地 
        a[0]   = '.';
        a[n+1] = '.';
        a[m+1] = '.';
    }
    int cnt = 0;
    for(int i = 1;i <= n ; i++){
        for(int j = 1;j <= m; j++){
            
            cin>>a[j];
            if(a[j]=='W'){
                c[cnt][0] = i;
                c[cnt][1] = j;
                cnt++;
            } 
        }
    }
    int step = 0;
    while(cnt){
        if(a[c[step][0]][c[step][1]] == 'W'){
            //有可能当前位置的水与前面搜刮的水联通被记为了陆地 以是要先判断一下
            //确定当前是一块未被搜刮过的 新 水  
            dfs(c[step][0],c[step][1]);
            ans++;//联通块个数加一 
        }
        step++;//搜刮下一个位置 
        cnt--;
    }
    
    cout<<ans;
    
    
    return 0;
}