本文涉及知识点

C++图论

LeetCode1391. 检查网格中是否存在有效路径

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。
你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。
注意：你 不能 变更街道。

如果网格中存在有效的路径，则返回 true，否则返回 false 。
示例 1：

输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。
示例 2：

输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。
示例 3：
输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。
示例 4：
输入：grid = [[1,1,1,1,1,1,3]]
输出：true
示例 5：
输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

并集查找

如果(0,0)和(m-1,n-1)在一个连通区域，则返回true;否则，返回false。
1，连接左右。
2，连接上下。
3，连接左下。
4，连接右下。
5，连接左上。
6，连接右上。

代码

核心代码

class CUnionFind
{
public:
	CUnionFind(int iSize) :m_vNodeToRegion(iSize)
	{
		for (int i = 0; i < iSize; i++)
		{
			m_vNodeToRegion[i] = i;
		}
		m_iConnetRegionCount = iSize;
	}	
	CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
	{
		for (int i = 0; i < vNeiBo.size(); i++) {
			for (const auto& n : vNeiBo[i]) {
				Union(i, n);
			}
		}
	}
	int GetConnectRegionIndex(int iNode)
	{
		int& iConnectNO = m_vNodeToRegion[iNode];
		if (iNode == iConnectNO)
		{
			return iNode;
		}
		return iConnectNO = GetConnectRegionIndex(iConnectNO);
	}
	void Union(int iNode1, int iNode2)
	{
		const int iConnectNO1 = GetConnectRegionIndex(iNode1);
		const int iConnectNO2 = GetConnectRegionIndex(iNode2);
		if (iConnectNO1 == iConnectNO2)
		{
			return;
		}
		m_iConnetRegionCount--;
		if (iConnectNO1 > iConnectNO2)
		{
			UnionConnect(iConnectNO1, iConnectNO2);
		}
		else
		{
			UnionConnect(iConnectNO2, iConnectNO1);
		}
	}

	bool IsConnect(int iNode1, int iNode2)
	{
		return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
	}
	int GetConnetRegionCount()const
	{
		return m_iConnetRegionCount;
	}
	vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
	{
		const int iNodeSize = m_vNodeToRegion.size();
		vector<int> vRet(iNodeSize);
		for (int i = 0; i < iNodeSize; i++)
		{
			vRet[GetConnectRegionIndex(i)]++;
		}
		return vRet;
	}
	std::unordered_map<int, vector<int>> GetNodeOfRegion()
	{
		std::unordered_map<int, vector<int>> ret;
		const int iNodeSize = m_vNodeToRegion.size();
		for (int i = 0; i < iNodeSize; i++)
		{
			ret[GetConnectRegionIndex(i)].emplace_back(i);
		}
		return ret;
	}
private:
	void UnionConnect(int iFrom, int iTo)
	{
		m_vNodeToRegion[iFrom] = iTo;
	}
	vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
	int m_iConnetRegionCount;
};


class Solution {
		public:
			bool hasValidPath(vector<vector<int>>& grid) {
				const int R = grid.size();
				const int C = grid[0].size();
				const int iMaskCount = R * C;
				auto Mask = [&](int r, int c) {return C * r + c; };
				auto CanRight = [](int s) {return (1 == s) || (4 == s) || (6 == s); };
				auto CanLeft = [](int s) {return (1 == s) || (3 == s) || (5 == s); };
				auto CanUp = [](int s) {return (2 == s) || (4 == s) || (6 == s); };
				auto CanDown = [](int s) {return (2 == s) || (3 == s) || (4 == s); };
				CUnionFind uf(iMaskCount);
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						auto AddLeft = [&]() {
							const int c1 = c -1;
							if ((c1 < 0) || (c1 >= C)) { return; }
							if (!CanRight(grid[r][c1])) { return; }
							uf.Union(Mask(r, c), Mask(r, c1));
						};
						auto AddRight = [&]() {
							const int c1 = c + 1;
							if ((c1 < 0) || (c1 >= C)) { return; }
							if (!CanLeft(grid[r][c1])) { return; }
							uf.Union(Mask(r, c), Mask(r, c1));
						};
						auto AddUp = [&]() {
							const int r1 = r -1;
							if ((r1 < 0) || (r1 >= R)) { return; }
							if (!CanDown(grid[r1][c])) { return; }
							uf.Union(Mask(r, c),Mask(r1, c));
						};
						auto AddDown = [&]() {
							const int r1 = r + 1;
							if ((r1 < 0) || (r1 >= R)) { return; }
							if (!CanUp(grid[r1][c])) { return; }
							uf.Union(Mask(r, c), Mask(r1, c));
						};
						switch (grid[r][c])
						{
						case 1 : 
							AddRight(); AddLeft();
							break;
						case 2:
							AddDown(); AddUp();
							break;
						case 3:
							AddLeft(); AddDown();
							break;
						case 4:
							AddRight(); AddDown();
							break;
						case 5:
							AddLeft(); AddUp();
							break;
						case 6:
							AddRight(); AddUp();
							break;
						default:
							break;
						}
					}
				}
				return uf.GetConnectRegionIndex(0) == uf.GetConnectRegionIndex(iMaskCount - 1);
			}
		};

单元测试

	vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {2,4,3},{6,5,2} };
			auto res = Solution().hasValidPath(grid);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {1,2,1},{1,2,1} };
			auto res = Solution().hasValidPath(grid);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1,1,2} };
			auto res = Solution().hasValidPath(grid);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod14)
		{
			grid = { {1,1,1,1,1,1,3} };
			auto res = Solution().hasValidPath(grid);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod15)
		{
			grid = { {2},{2},{2},{2},{2},{2},{6} };
			auto res = Solution().hasValidPath(grid);
			AssertEx(true, res);
		}