読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

【蟻本】Lake Counting

// 蟻本p.35
// Lake Counting(POJ No.2386)
// 深さ優先探索で同じ文字を消していく問題

#include <bits/stdc++.h>
using namespace std;

static const int MAX_N = 100;
static const int MAX_M = 100;
char field[MAX_N][MAX_M];
int n,m;
int dx[8]={1,1,0,-1,-1,-1,0,1},dy[8]={0,1,1,1,0,-1,-1,-1};

void dfs(int y,int x)
{
    field[y][x] = '.';
    for(int i=0;i<8;i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(0<=nx && nx<m && 0<=ny && ny<n && field[ny][nx]=='W'){
            dfs(ny,nx);
        }
    }
}

int main()
{
    int cnt = 0;
    //INPUT
    cin>>n>>m;
    string tmp;
    for(int i=0;i<n;i++){
        cin>>tmp;
        for(int j=0;j<m;j++){
            field[i][j] = tmp[j];
        }
    }
    //depth first search
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(field[i][j]=='W'){
                cnt += 1;
                //周囲の'W'を消していく
                dfs(i,j);
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}