题目描述

点一遍0的连通块 + 点一遍周围雷数量1-8的点 = 最少的点击量

样例

import java.util.*;

public class Main {

    static final int N = 310;
    static int n;
    //存储矩阵
    static char[][] str = new char[N][N];
    //存储每个点周围雷的数量
    static int[][] g = new int[N][N];

    static void dfs(int a, int b) {
        int t = g[a][b];
        //这里标记成-1，方便一点，只要不是1-8或0的数 代表点为0的块已经被扫过了
        g[a][b] = -1;
        //如果不是零，就返回，只有0才能继续扩展
        if (t != 0) return;

        //枚举八个方向(如何扫八个方向)
        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 && g[x][y] != -1)
                    dfs(x, y);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int cases = 1; cases <= T; cases++) {
            n = scanner.nextInt();
            for (int i = 0; i < n; i++)
                str[i] = scanner.next().toCharArray();

            //
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    //如果当前位置是雷
                    if (str[i][j] == '*')
                        //用-1表示
                        g[i][j] = -1;
                    else {//否则统计周围八个方向雷的数量
                        g[i][j] = 0;
                        for (int x = i - 1; x <= i + 1; x++)
                            for (int y = j - 1; y <= j + 1; y++)
                                //如果没有越界，且出现了雷，g[i][j]++
                                if (x >= 0 && x < n && y >= 0 && y < n && str[x][y] == '*')
                                    g[i][j]++;
                    }

            int res = 0;

            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    //如果这个点为0，说明没有雷
                    if (g[i][j] == 0) {
                        //点的次数+1
                        res++;
                        //从当前的点做一下flood fill 标记一下相邻的0
                        dfs(i, j);
                    }

            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    //找1-8的数
                    if (g[i][j] != -1)
                        //点的次数+1
                        res++;

            System.out.println("Case #" + cases + ": " + res);
        }
    }
}