本文涉及知识点

C++BFS算法

LeetCode1210. 穿过迷宫的最少移动次数

你还记得那条风靡全球的贪吃蛇吗？
我们在一个 n*n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（(0, 0) 和 (0, 1)）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（(n-1, n-2) 和 (n-1, n-1)）。
每次移动，蛇可以这样走：
如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c+1)）移动到 （(r, c)、(r+1, c)）。

如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。

返回蛇抵达目的地所需的最少移动次数。
如果无法到达目的地，请返回 -1。
示例 1：
输入：grid = [[0,0,0,0,0,1],
[1,1,0,0,1,0],
[0,0,0,0,1,1],
[0,0,1,0,1,0],
[0,1,1,0,0,0],
[0,1,1,0,0,0]]
输出：11
解释：

一种可能的解决方案是 [右, 右, 顺时针旋转, 右, 下, 下, 下, 下, 逆时针旋转, 右, 下]。
示例 2：
输入：grid = [[0,0,1,1,1,1],
[0,0,0,0,1,1],
[1,1,0,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,0]]
输出：9
提示：
2 <= n <= 100
0 <= grid[i][j] <= 1
蛇保证从空单元格开始出发。

BFS

BFS的状态表示{r,c,k} 表示蛇头处于(r,c)，k为0水平，为1竖直。空间复杂度：O(mn)。
BFS的后续状态：移动或旋转。单个状态的时间复杂度：O(1)，总时间复杂度：O(mn)。
dis[r][c][k]记录到达此状态需要的步数，-1表示未处理。
注意：水平状态，蛇头永远在右边；竖直状态，蛇头永远在下。
水平状态也可以下移。
最终状态是：蛇头在(r-1,c-1)且水平。

代码

核心代码

class Solution {
		public:
			int minimumMoves(vector<vector<int>>& grid) {
				const int R = grid.size();
				const int C = grid[0].size();
				const int iNotMay = 1'000'000'000;
				vector<vector<vector<int>>> vDis(R, vector<vector<int>>(C, vector<int>(2, iNotMay)));
				queue<tuple<int, int, int>> que;
				auto Add = [&](int r, int c, int k, int dis) {
					if (iNotMay != vDis[r][c][k])return;
					vDis[r][c][k] = dis;
					que.emplace(r, c, k);
				};
				auto CanRight = [&](int r, int c) {
					return (c + 1 < C) && (grid[r][c + 1] == 0);
				};
				auto CanDown = [&](int r, int c) {
					return (r + 1 < R) && (grid[r + 1][c] == 0);
				};
				Add(0, 1, 0, 0);
				while (que.size()) {
					auto [r, c, k] = que.front();
					que.pop();
					const int dis1 = vDis[r][c][k] + 1;
					if (0 == k) {
						if (CanRight(r, c)) { Add(r, c + 1, k, dis1); }
						if (CanDown(r, c) && CanDown(r, c - 1)) {
							Add(r + 1, c-1 , 1, dis1);
							Add(r + 1, c, k, dis1);
						}
					}
					else {
						if (CanDown(r, c)) { Add(r + 1, c , k, dis1); }
						if (CanRight(r, c) && CanRight(r-1, c)) { 
							Add(r - 1, c + 1, 0, dis1);
							Add(r  , c + 1, k, dis1);
						}
					}
				}
				auto ans = vDis.back().back()[0];
				return iNotMay == ans ? -1 : ans;;
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod1)
		{
			grid = { {0,0} };
			auto res = Solution().minimumMoves(grid);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod2)
		{
			grid = { {0,0,0} };
			auto res = Solution().minimumMoves(grid);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod3)
		{
			grid = { {0,0},{0,0} };
			auto res = Solution().minimumMoves(grid);
			AssertEx(1, res);
		}
	
		TEST_METHOD(TestMethod11)
		{
			grid = { {0,0,0,0,0,1},
			   {1,1,0,0,1,0},
			   {0,0,0,0,1,1},
			   {0,0,1,0,1,0},
			   {0,1,1,0,0,0},
			   {0,1,1,0,0,0} };
			auto res = Solution().minimumMoves(grid);
			AssertEx(11, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {0,0,1,1,1,1},
			   {0,0,0,0,1,1},
			   {1,1,0,0,0,1},
			   {1,1,1,0,0,1},
			   {1,1,1,0,0,1},
			   {1,1,1,0,0,0} };
			auto res = Solution().minimumMoves(grid);
			AssertEx(9, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid.assign(4, vector<int>(4));
			auto res = Solution().minimumMoves(grid);
			AssertEx(5, res);
		}