题解 | #Lake Counting#

这道题可以用dfs也可以用bfs，这里选用bfs。

思路：找到一个W，然后使劲的往下搜，每搜到一个点就把W变成.，直到搜不了。然后再找一个W……（禁止套娃（doge)）

#include <iostream>
using namespace std;

const int N = 105;

struct node {
    int x, y;
}q[N * N];//结构体数组模拟队列，也可以用STLqueue

char a[N][N];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};//坐标增减
int n, m, res;

void bfs(int x0, int y0) {//广搜板子
    q[1] = {x0, y0};
    a[x0][y0] = '.';
    int head = 0, tail = 1;
    while (head < tail) {
        head ++;
        for (int i = 0; i < 8; i ++) {
            int x = q[head].x + dx[i];
            int y = q[head].y + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] == 'W') {
                tail ++;
                q[tail] = {x, y};
                a[x][y] = '.';
            }
        }
    }    
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> a[i][j];
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++) {
            if (a[i][j] == 'W') {//判断是否是W
                bfs(i, j);//传入W的坐标
                res ++;//一个湖搜完了，res+1
            }
        }
    cout << res << endl;
    return 0;//完美结束
}

无注释版本

#include <iostream>
using namespace std;

const int N = 105;

struct node {
    int x, y;
}q[N * N];

char a[N][N];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n, m, res;

void bfs(int x0, int y0) {
    q[1] = {x0, y0};
    a[x0][y0] = '.';
    int head = 0, tail = 1;
    while (head < tail) {
        head ++;
        for (int i = 0; i < 8; i ++) {
            int x = q[head].x + dx[i];
            int y = q[head].y + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] == 'W') {
                tail ++;
                q[tail] = {x, y};
                a[x][y] = '.';
            }
        }
    }    
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> a[i][j];
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++) {
            if (a[i][j] == 'W') {
                bfs(i, j);
                res ++;
            }
        }
    cout << res << endl;
    return 0;
}