体力活般的DFS
#include <iostream>
#include <vector>
using namespace std;
static constexpr int dirs[][2] {{0, -1}, {-1, -1}, {-1, 0}, {-1, 1},
{0, 1}, {1, 1}, {1, 0}, {1, -1}};
int t, n;
// depth first search algorithm
void dfs(vector<vector<int>>& g, int x, int y) {
// recursion exit condition
if (x < 0 || y < 0 || x == n || y == n || g[y][x] == -1)
return;
const int t = g[y][x];
g[y][x] = -1; // mark as seen
if (t) return;
for (const auto& d : dirs)
dfs(g, x + d[0], y + d[1]);
}
// debug helper function
void printGrid(vector<vector<int>>& g) {
const int n = g.size();
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) printf("%3d", g[y][x]);
printf("\n");
}
}
int main(void) {
cin >> t;
for (int i = 1; i <= t; ++i) {
cin >> n;
vector<vector<char>> grid(n, vector<char>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) cin >> grid[i][j];
// 先统计每个点的周围的雷的个数
vector<vector<int>> g(n, vector<int>(n, 0));
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x) {
if (grid[y][x] == '*') {
g[y][x] = -1;
continue;
}
g[y][x] = 0;
for (int r = max(0, y - 1); r < min(n, y + 2); ++r)
for (int c = max(0, x - 1); c < min(n, x + 2); ++c)
g[y][x] += grid[r][c] == '*';
}
int ans = 0;
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x)
if (!g[y][x]) {
dfs(g, x, y);
++ans;
}
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x)
ans += g[y][x] != -1;
printf("Case #%d: %d\n", i, ans);
}
}