算法1

(dfs递归 FloodFills) $O(n^2)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 310;

int n, T;
int B[N][N];
char g[N][N];

void dfs(int a, int b)
{
    int t = B[a][b];
    B[a][b] = -1;
    if(t) return;
    else
    {
        for(int x = a - 1; x <= a + 1; x ++)
            for(int y = b - 1; y <= b + 1; y ++)
                if(x >= 0 && x < n && y >= 0 && y < n && B[x][y] != -1)
                    dfs(x, y);
    }
}

int main()
{
    scanf("%d", &T);
    for(int c = 1; c <= T; c ++)
    {
        int res = 0;

        scanf("%d", &n);
        for(int i = 0; i < n; i ++) scanf("%s", g[i]);

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                if(g[i][j] == '*') B[i][j] = -1;
                else
                {
                    B[i][j] = 0;
                    for(int x = i - 1; x <= i + 1; x ++)
                        for(int y = j - 1; y <= j + 1; y ++)
                            if(x >= 0 && x < n && y >= 0 && y < n && g[x][y] == '*')
                                B[i][j] ++;
                }

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                if(B[i][j] == 0)
                {
                    res ++;
                    dfs(i, j);
                }

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                if(B[i][j] != -1)
                    res ++;

        printf("Case #%d: %d\n", c, res);
    }
}