本文涉及的知识点

C++BFS算法

LeetCode1905. 统计子岛屿

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的 数目 。

示例 1：

输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
示例 2：

输入：grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
输出：2
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。

提示：

m == grid1.length == grid2.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500
grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1 。

C++BFS

将已处理的单格设置为-1。通过BFS获取grid[r][c]==1所在的岛屿。判断此岛屿所有单格在gird1中，是否全部是陆地。
会不会gird2的某个岛屿d1，被grid1的两个岛屿d2、d3包括？ 不会。
令c2和c3都在d1中，且c2在d2,c3在d3中。由于c2和c3都在d1，故其连通。由于c2在d2，c3在d3，故d2和d3连通。
BFS的初始状态：leves[0] = {rootr,rootc}。
BFS的的状态表示：leves[i]记录距离root为i的所有陆地单格。
BFS的后续状态：通过next访问cur的临接表。四联通临接表，前续单格和后续单格必须都是陆地。
BFS的返回值：无。
BFS的重复处理：gird出重。
BFS的优化：一维数组代替二维数组。

代码

核心代码

class Solution {
		public:
			int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
				auto vilid = [&](int r, int c) {return grid2[r][c] == 1; };
				CGrid grid(grid2.size(), grid2.front().size());
				auto neiBo = grid.NeiBo(vilid, vilid);
				int ret = 0;
				grid.EnumGrid([&](int r, int c) {
					if (1 != grid2[r][c])return ;
					vector<pair<int, int>> v = { {r,c} };
					for (int i = 0; i < v.size(); i++) {
						const int iMask = grid.Mask(v[i].first, v[i].second);
						for (const auto& [r, c] : neiBo[iMask]) {
							if (1 != grid2[r][c]) { continue; }
							grid2[r][c] = -1;
							v.emplace_back(r, c);
						}
					}
					for (const auto& [r, c] : v) {
						if (1 != grid1[r][c]) { return; }
					}
					ret++;
				});
				return ret;
			}
		};

单元测试

vector<vector<int>> grid1, grid2;
		TEST_METHOD(TestMethod11)
		{
			grid1 = { {1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1} }, grid2 = { {1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0} };
			auto res = Solution().countSubIslands(grid1, grid2);
			AssertEx(res, 3);
		}
		TEST_METHOD(TestMethod12)
		{
			grid1 = { {1,0,1,0,1},{1,1,1,1,1},{0,0,0,0,0},{1,1,1,1,1},{1,0,1,0,1} }, grid2 = { {0,0,0,0,0},{1,1,1,1,1},{0,1,0,1,0},{0,1,0,1,0},{1,0,0,0,1} };
			auto res = Solution().countSubIslands(grid1, grid2);
			AssertEx(res, 2);
		}