思路

相当于开了透视，先把0的都点了，然后点剩下的

深搜

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 310;

int T, n;
char g[N][N];
int t[N][N];
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

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

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

        //统计每个点周围雷的个数
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                if (g[i][j] == '*')
                {
                    t[i][j] = -1;
                }
                else
                {
                   for(int k=0; k<8; k++)
                    {
                        int a = i + dx[k], b = j + dy[k];
                        if (a >=0 && a < n && b >= 0 && b < n && g[a][b] == '*')
                        {
                            // cout << i << j<< a << b << endl;
                            t[i][j]++;
                        }
                    } 
                    // cout << t[i][j] << endl;
                }

            }
        }

        //先把所有0的地方点了然后扩展
        int res = 0;
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                if (t[i][j] == 0)
                {
                   res++; 
                   dfs(i, j);
                }
            }
        }

        //点剩下的地方
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                if (t[i][j] != -1)
                    res++;
            }
        }
        printf("Case #%d: %d\n", i, res);
        memset(t, 0, sizeof(t));
    }
    return 0;
}