L2-048 寻宝图（PTA）

L2-048 寻宝图

题目描述

给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有多少岛屿，其中有多少是有宝藏的岛屿。

输入格式：
输入第一行给出 2 个正整数 N 和 M（15 ），是地图的尺寸，表示地图由 N 行 M 列格子构成。随后 N 行，每行给出 M 位个位数，其中 0 表示水域，1 表示陆地，2-9 表示宝藏。
注意：两个格子共享一条边时，才是“相邻”的。宝藏都埋在陆地上。默认地图外围全是水域。

输出格式：
在一行中输出 2 个整数，分别是岛屿的总数量和有宝藏的岛屿的数量。

输入样例：

10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001
1
2
3
4
5
6
7
8
9
10
11

输出样例：

7 2
1

bfs

以下是对于上述代码的详细注释，解释了代码的每一个部分的功能和目的：

#include // 包含几乎所有常用的库，方便快捷但不推荐在大型项目中使用
using namespace std;

const int z=1e5+10; // 定义常量z作为地图的最大尺寸

string g[z]; // 定义一个字符串数组g，用于存储地图的每一行
int dx[]={0,0,-1,1}; // 定义x方向的移动数组，表示上下左右移动
int dy[]={-1,1,0,0}; // 定义y方向的移动数组，表示上下左右移动
typedef pair<int,int> pii; // 定义pii为pair的别名，用于存储坐标

int main()
{
	int n,m; // 定义n和m分别表示地图的行数和列数
	int ans=0,cnt=0; // ans用来计数岛屿总数，cnt用来计数有宝藏的岛屿数量
	cin>>n>>m; // 读入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') // 如果当前位置不是水域
			{
				ans++; // 岛屿总数加1
				queue<pii> p; // 定义一个队列p，用于宽度优先搜索(BFS)
				p.push({i,j}); // 将当前坐标加入队列
				int flag=0; // 定义flag标志是否找到宝藏
				if(g[i][j]>'1') flag=1; // 如果当前位置是宝藏，设置flag为1
				g[i][j]='0'; // 将当前位置标记为已访问
				while(p.size()) // 当队列不为空时循环
				{
					auto t=p.front(); // 获取队列前面的元素
					p.pop(); // 弹出队列前面的元素
					for(int k=0;k<4;k++) // 查看四个方向的相邻位置
					{
						int tx=t.first+dx[k]; // 计算x方向的新坐标
						int ty=t.second+dy[k]; // 计算y方向的新坐标
						if(tx>=0&&tx<n&&ty>=0&&ty<m&&g[tx][ty]!='0') // 如果新坐标在地图内且不是水域
						{
							if(g[tx][ty]>'1') flag=1; // 如果新坐标是宝藏，设置flag为1
							p.push({tx,ty}); // 将新坐标加入队列
							g[tx][ty]='0'; // 将新坐标标记为已访问
						}
					}
				}
				if(flag==1) cnt++; // 如果找到宝藏，有宝藏岛屿数加1
			}
		}
	}
	cout<<ans<<" "<<cnt; // 输出岛屿总数和有宝藏的岛屿数量
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

这段代码基本上实现了题目的要求：统计地图上的岛屿总数和有宝藏的岛屿数量。代码主体使用了宽度优先搜索（BFS）来探索每个岛屿，并且在探索的过程中检查岛屿上是否有宝藏。探索过程中，为了避免重复访问，会将访问过的陆地点标注为水域（‘0’）。如果在探索特定岛屿的过程中遇到标记数值大于’1’的格子，则认为这个岛屿含有宝藏。

踩到的坑

1. 我对宝藏的判断只放在了从第一个陆地进来后开始拓展的bfs中，漏掉了万一进来时候就是宝藏的情况
   例如：从2（宝藏）进来时我就漏掉了这种情况

211
110
100
1
2
3

2. 段错误：我一开始还加了一个字符串d（string d[z]），用来判断当前位置有没有遍历过，开了两个太大的字符串，最后两个测试点出现的段错误