题目描述

blablabla

样例

#include <iostream>

using namespace std;

const int N =1005;
int n, m;
char g[N][N];
int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int ans;

int bfs(int x, int y) {
    g[x][y] = '.';
    for (int i = 0 ; i < 8 ; i ++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || yy < 1 || xx > n || yy > m || g[xx][yy] == '.') {
            continue;
        }
        bfs(xx, yy);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1; j <= m ; j ++) {
            cin >> g[i][j];
        }
    }

    for (int i = 1; i <= n ; i ++) {
        for (int j = 1; j <= m ; j ++) {
            if (g[i][j] == '.') continue;
            else if (g[i][j] == 'W'){
                bfs(i, j);
                ans ++ ;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla