家族数就是网格里字母格的四连通块个数：扫描到未访问的字母格就计数 +1 并洪水填充染色。
OJ: roj
题目 ID: 8016
难度:入门
标签:dfs搜索连通块
创建: 2026-10-02 17:12
更新: 2026-10-06 17:02
题目描述
岛屿地图有 *（河流或山丘）或小写字母（一户人家），上下左右共边的两户算相邻，互相可达的人家属于同一个家族，求家族个数。输入第一行是
plaintext
输入： 输出：
4 3
*zlw**pxh
l*zlwk*hx*
w*tyy**yyy
zzl思路
家族就是字母格子的四连通块，* 和空格都是断开的障碍。从左到右、从上到下扫描，遇到未访问的字母格就把答案 +1，并用显式栈的洪水填充把整个连通块染色（长链可能让递归爆栈）。注意读入必须保留行首空格，越界按每行实际长度判断。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 17:15
# update_at: 2026-10-02 17:15
import sys
def flood_fill(start: tuple[int, int], grid: list[str], seen: set[tuple[int, int]]) -> None:
"""从 start 出发，把上下左右连通的同一片字母区域全部标记为已访问。"""
stack = [start]
while stack:
x, y = stack.pop()
for adj in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
nx, ny = adj
in_map = 0 <= nx < len(grid) and 0 <= ny < len(grid[nx])
if in_map and grid[nx][ny].isalpha() and adj not in seen:
seen.add(adj) # 入栈前先标记，避免同一个格子被重复入栈
stack.append(adj)
def solve() -> None:
lines = sys.stdin.read().splitlines()
n = int(lines[0])
grid = lines[1:n + 1] # 每行原样保留前导空格：空格是大海，'*' 是阻隔，字母是人家
seen: set[tuple[int, int]] = set()
families = 0
for r, row in enumerate(grid):
for c, ch in enumerate(row):
if ch.isalpha() and (r, c) not in seen:
families += 1 # 发现一个没访问过的字母点，就多了一个新家族
flood_fill((r, c), grid, seen)
print(families)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 17:02
* update_at: 2026-10-06 17:02
*/
#include <cstdio>
#include <string>
#include <stack>
using namespace std;
typedef long long ll;
const int MAXN = 105; // 行数上限
const int MAXM = 205; // 每行字符数上限
int n; // 地图行数
int len[MAXN]; // len[i] 表示第 i 行实际存了几个字符
char grid[MAXN][MAXM]; // grid[i][j] 存地图字符，下标从 0 开始
bool vis[MAXN][MAXM]; // vis[i][j] 表示该字母格是否已被染过色
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// 洪水填充：从 (r, c) 出发把整个家族的字母格都标记成已访问
// 用显式栈写成迭代 DFS，避免长链递归爆栈
void flood(int r, int c) {
stack< pair<int, int> > st;
st.push(make_pair(r, c));
vis[r][c] = true; // 入栈前先标记，防止重复入栈
while (!st.empty()) {
int x = st.top().first;
int y = st.top().second;
st.pop();
// 枚举上下左右四个方向的字母格
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= len[nx]) continue; // 越界（各行长度不同）
if (vis[nx][ny]) continue;
if (grid[nx][ny] < 'a' || grid[nx][ny] > 'z') continue; // 只走字母格
vis[nx][ny] = true;
st.push(make_pair(nx, ny));
}
}
}
int main() {
scanf("%d", &n);
// getchar 吃掉数字后面的换行
getchar();
for (int i = 0; i < n; ++i) {
// 用 fgets 逐行读入，保留行首空格（大海）
fgets(grid[i], MAXM, stdin);
len[i] = 0;
// fgets 可能把末尾换行读进来，统一截掉
while (grid[i][len[i]] != '\0' && grid[i][len[i]] != '\n' && grid[i][len[i]] != '\r') {
++len[i];
}
grid[i][len[i]] = '\0';
}
int ans = 0; // 家族数：每发现一个未访问的字母格就 +1
for (int i = 0; i < n; ++i) {
for (int j = 0; j < len[i]; ++j) {
if (!vis[i][j] && grid[i][j] >= 'a' && grid[i][j] <= 'z') {
++ans;
flood(i, j);
}
}
}
printf("%d\n", ans);
return 0;
}