P1596 [USACO10OCT]Lake Counting S

P1596 [USACO10OCT]Lake Counting S

 

 

#include<bits/stdc++.h>
using namespace std;
int dir[8][2]={
    {1,1},
    {1,-1},
    {1,0},
    {0,1},
    {0,-1},
    {-1,-1},
    {-1,0},
    {-1,1}
};
char maps[101][101];
int ans,n,m;
bool check(int x,int y)
{
    return x>=0&&x<n&&y>=0&&y<m&&maps[x][y]=='W';
}
void dfs(int x,int y)
{
    maps[x][y]='.';//表示访问过
    int newx,newy;
    for(int i=0;i<8;i++){
        newx=x+dir[i][0];
        newy=y+dir[i][1];
        if(check(newx,newy)){
            dfs(newx,newy);
        }
    }
    return;
}
int main()
{
    ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>maps[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maps[i][j]=='W'){
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

 

上一篇:OCP 062【中文】考试题库(cuug内部资料)第20题


下一篇:「ACM Shenyang Onsite 2016」E.Counting Cliques(dfs暴力+优化)