1. 题目描述
给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有多少岛屿，其中有多少是有宝藏的岛屿。
输入格式：
输入第一行给出 2 个正整数 N 和 M（1<N×M≤105），是地图的尺寸，表示地图由 N 行 M 列格子构成。随后 N 行，每行给出 M 位个位数，其中 0 表示水域，1 表示陆地，2-9 表示宝藏。
注意：两个格子共享一条边时，才是“相邻”的。宝藏都埋在陆地上。默认地图外围全是水域。
输出格式：
在一行中输出 2 个整数，分别是岛屿的总数量和有宝藏的岛屿的数量。
输入样例：
10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001
AI 代码解读
输出样例：
7 2
AI 代码解读
2. 思路分析
联通块flood-fill问题。这题需要特别注意 1<N×M≤10^5 这个条件，所以我们不能用二维数组来直接存储（因为有可能其中一维为10^5，另一维为1，所以理论上二维数组每一维都要为10^5，但是很明显会爆，二维数组开不了这么大的空间（也就不能用二维数组读入，也不能开一个二维数组来标记，所以我就用了“染色”的思想）...为了解决这个问题，这题我采用了每一行用一个字符串存储来读入）。
联通块问题可以用DFS或BFS来解决。这里我用了深度优先搜索DFS，用ans统计总岛屿数量，ans1统计有宝藏的岛屿数量。遇到一个非'0'字符（也就是'1'和 宝藏'2'到'9'）就让ans++，同时将这个非'0'字符染色为'0'，然后往四个方向（上、下、左、右）搜索，这里的目的是那一片岛屿（也就是那一片为'1'的部分）都染色为‘0’。
为了判断有宝藏的岛屿，这里我开了一个全局变量f来判断这一片岛屿是否有宝藏（也就是有无字符'2'-'9'），当搜到字符'2'~'9'时就将f标记为1。
为了实现上、下、左、右搜索，这里我开了两个方向数组dx[ ]和dy[ ] 存储坐标（x,y）上、下、左、右 表示下一步能到的位置。如果越界或者下一步搜到字符'0'时就跳过。
每次搜索完时，如果f为1，就让ans1++，同时再将f置为0，便于以后的搜索。
3. 代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5+10;
int n, m;
ll ans, ans1;
string g[N];
int dx[] = {
-1,1,0,0 };
int dy[] = {
0,0,-1,1 };
int f;
void dfs(int x, int y) {
if (g[x][y] >= '2' && g[x][y] <= '9') f = 1;
g[x][y] = '0';
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx<0 || nx>n - 1 || ny<0 || ny>m - 1) continue;
if (g[nx][ny] == '0') continue;
dfs(nx, ny);
}
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] != '0') {
dfs(i, j);
ans++;
}
if (f) {
ans1++;
f = 0;
}
}
}
cout << ans << " " << ans1 << endl;
return 0;
}
AI 代码解读
