本文涉及知识点

C++BFS算法
C++图论

LeetCode1254统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。
示例 1：

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
示例 2：
输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1
示例 3：
输入：grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
输出：2
提示：
1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

BFS

第i次发现gird[r][c]为0，则BFS将和(r,c)直接或间接相邻的陆地设置为10+i。如果BFS的过程遇到边界，则将ret设置为false。BFS结束时，返回ret。表示是否是封闭岛屿。遇到边界不能直接返回，否则未处理的部分会看成第二个岛。
也可以分两步：
一，利用BFS将和边界相连的陆地全部改成水。
二，统计岛屿数量。

代码

核心代码

class CGrid {
public:
	CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}
	template<class Fun1,class Fun2>
	vector<vector<pair<int, int>>> NeiBo(Fun1 funVilidCur, Fun2 funVilidNext, int iConnect = 4)
	{
		vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				if (!funVilidCur(r, c))continue;
				auto& v = vNeiBo[Mask(r, c)];
				if ((r > 0)&& funVilidNext(r-1, c)) {
					v.emplace_back(r-1, c);
				}
				if ((c > 0) && funVilidNext(r , c - 1)) {
					v.emplace_back(r, c - 1);
				}
				if ((r+1 < m_r ) && funVilidNext(r + 1, c)) {
					v.emplace_back(r + 1, c);
				}
				if ((c+1 <m_c ) && funVilidNext(r, c + 1)) {
					v.emplace_back(r, c + 1);
				}
			}
		}
		return vNeiBo;
	}
	vector<vector<int>> Dis( vector<pair<int, int>> start, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, const int& iConnect = 4) {
		static short dir[8][2] = { {0, 1}, {1, 0}, {-1, 0},{ 0, -1},{1,1},{1,-1},{-1,1},{-1,-1} };
		vector<vector<int>> vDis(m_r, vector<int>(m_c, -1));
		for (const auto& [r, c] : start) {
			vDis[r][c] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			const auto [r, c] = start[i];
			if (!funVilidCur(r, c)) { continue; }
			for (int k = 0; k < iConnect; k++) {
				const int r1 = r + dir[k][0];
				const int c1 = c + dir[k][1];
				if ((r1 < 0) || (r1 >= m_r) || (c1 < 0) || (c1 >= m_c)) { continue; }
				if (funVilidNext(r1, c1) && (-1 == vDis[r1][c1])) {
					start.emplace_back(r1, c1);
					vDis[r1][c1] = vDis[r][c] + 1;
				}
			}
		}
		return vDis;
	}
	 void EnumGrid(std::function<void(int, int)> call)
	{
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				call(r, c);
			}
		}
	}	
	 vector<pair<int, int>> GetPos(std::function<bool(int, int)> fun) {
		 vector<pair<int, int>> ret;
		 for (int r = 0; r < m_r; r++)
		 {
			 for (int c = 0; c < m_c; c++)
			 {
				 if (fun(r, c)) {
					 ret.emplace_back(r, c);
				 }
			 }
		 }
		 return ret;
	 }
	inline int Mask(int r, int c) { return  m_c * r + c; }
	const int m_r, m_c;
	const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
};

class Solution {
		public:
			int closedIsland(vector<vector<int>>& grid) {
			auto Vilid =[&](int r, int c) {return true; };		
			CGrid gn(grid.size(), grid[0].size());
			auto neiBo = gn.NeiBo(Vilid, Vilid);
			auto BFS1 = [&](int r, int c) {						
				queue<pair<int, int>> que;
				auto Add = [&](int r, int c) {
					if (0 !=grid[r][c]) { return; }
					que.emplace(r, c);
					grid[r][c] = 1;
				};		
				Add(r, c);	
				while (que.size()) {
					auto [curr, curc] = que.front();
					que.pop();
					for ( auto [nr, nc] : neiBo[gn.Mask(curr,curc)]) {
						Add(nr, nc);
					}
				}
			};
			auto BFS2 = [&](int r, int c) {
				queue<pair<int, int>> que;
				auto Add = [&](int r, int c) {
					if (0 != grid[r][c]) { return; }
					que.emplace(r, c);
					grid[r][c] = 2;
				};
				Add(r, c);
				bool b = que.size();
				while (que.size()) {
					auto [curr, curc] = que.front();
					que.pop();
					for (auto [nr, nc] : neiBo[gn.Mask(curr, curc)]) {
						Add(nr, nc);
					}
				}
				return b;
			};
			for (int r = 0; r < gn.m_r; r++) {
				BFS1(r, 0);
				BFS1(r, gn.m_c - 1);
			}
			for (int c = 0; c < gn.m_c; c++) {
				BFS1(0, c);
				BFS1(gn.m_r - 1, c);
			}
			int ans = 0;
			for (int r = 0; r < gn.m_r; r++) {
				for (int c = 0; c < gn.m_c; c++) {
					ans += BFS2(r, c);
				}
			}
			return ans;
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0,1},{1,1,1,1,1,1,1,0} };
			auto res = Solution().closedIsland(grid);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {0,0,1,0,0},{0,1,0,1,0},{0,1,1,1,0} };
			auto res = Solution().closedIsland(grid);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1,1,1,1,1,1,1},
			 {1,0,0,0,0,0,1},
			 {1,0,1,1,1,0,1},
			 {1,0,1,0,1,0,1},
			 {1,0,1,1,1,0,1},
			 {1,0,0,0,0,0,1},
			 {1,1,1,1,1,1,1} };
			auto res = Solution().closedIsland(grid);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			grid = { {0,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,1,0,0,1,0},{1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0} };
			auto res = Solution().closedIsland(grid);
			AssertEx(0, res);
		}