【广度优先搜索】【网格】【割点】1263. 推箱子

作者推荐

视频算法专题

涉及知识点

广度优先搜索 网格 割点 并集查找

LeetCode:1263. 推箱子

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。
现在你将作为玩家参与游戏，按规则将箱子 ‘B’ 移动到目标位置 ‘T’ ：
玩家用字符 ‘S’ 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
地板用字符 ‘.’ 表示，意味着可以自由行走。
墙用字符 ‘#’ 表示，意味着障碍物，不能通行。
箱子仅有一个，用字符 ‘B’ 表示。相应地，网格上有一个目标位置 ‘T’。
玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。
示例 1：
输入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],
[“#”,“T”,“#”,“#”,“#”,“#”],
[“#”,“.”,“.”,“B”,“.”,“#”],
[“#”,“.”,“#”,“#”,“.”,“#”],
[“#”,“.”,“.”,“.”,“S”,“#”],
[“#”,“#”,“#”,“#”,“#”,“#”]]
在这里插入图片描述

输出：3
解释：我们只需要返回推箱子的次数。
示例 2：
输入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],
[“#”,“T”,“#”,“#”,“#”,“#”],
[“#”,“.”,“.”,“B”,“.”,“#”],
[“#”,“#”,“#”,“#”,“.”,“#”],
[“#”,“.”,“.”,“.”,“S”,“#”],
[“#”,“#”,“#”,“#”,“#”,“#”]]
输出：-1
示例 3：
输入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],
[“#”,“T”,“.”,“.”,“#”,“#”],
[“#”,“.”,“#”,“B”,“.”,“#”],
[“#”,“.”,“.”,“.”,“.”,“#”],
[“#”,“.”,“.”,“.”,“S”,“#”],
[“#”,“#”,“#”,“#”,“#”,“#”]]
输出：5
解释：向下、向左、向左、向上再向上。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 20
grid 仅包含字符 ‘.’, ‘#’, ‘S’ , ‘T’, 以及 ‘B’。
grid 中 ‘S’, ‘B’ 和 ‘T’ 各只能出现一个。

01广度优先搜索

状态：箱子所在行列，人所在行列
人试图向上下左右移动。以左移为例。
{ 如果人可以左移，人左移，加到队首 箱子不在左边 如果人和箱子都可以左移，人箱子左移，加到队尾 箱子在人左边 {如果人可以左移，人左移，加到队首箱子不在左边如果人和箱子都可以左移，人箱子左移，加到队尾箱子在人左边

{如果人可以左移，人左移，加到队首如果人和箱子都可以左移，人箱子左移，加到队尾箱子不在左边箱子在人左边
{如果人可以左移，人左移，加到队首如果人和箱子都可以左移，人箱子左移，加到队尾​箱子不在左边箱子在人左边​
妙在无需考虑： 箱子对人的影响。

代码

核心代码

class CBFS
{
public:
	CBFS(int iStatuCount, int iInit = -1):m_iStatuCount(iStatuCount),m_iInit(iInit)
	{
		m_res.assign(iStatuCount, iInit);
	}
	bool Peek(int& statu)
	{
		if (m_que.empty())
		{
			return false;
		}
		statu = m_que.front();
		m_que.pop_front();
		return true;
	}
	void PushBack(int statu, int value)
	{
		if (m_iInit != m_res[statu])
		{
			return;
		}
		m_res[statu] = value;
		m_que.push_back(statu);
	}
	void PushFront(int statu, int value)
	{
		if (m_iInit != m_res[statu])
		{
			return;
		}
		m_res[statu] = value;
		m_que.push_front(statu);
	}
	int Get(int statu)
	{
		return m_res[statu];
	}
private:
	const int m_iStatuCount;
	const int m_iInit;
	deque<int> m_que;
	vector<int> m_res;
};

class CBFS2 : protected CBFS
{
public:
	CBFS2(int iStatuCount1,int iStatuCount2, int iInit = -1) :CBFS(iStatuCount1* iStatuCount2, iInit ), m_iStatuCount2(iStatuCount2)
	{
		
	}
	bool Peek(int& statu1,int& statu2 )
	{
		int statu;
		if (!CBFS::Peek(statu))
		{
			return false;
		}
		statu1 = statu / m_iStatuCount2;
		statu2 = statu % m_iStatuCount2;
		return true;
	}
	void PushBack(int statu1,int statu2, int value)
	{
		CBFS::PushBack(statu1 * m_iStatuCount2 + statu2, value);
	}
	void PushFront(int statu1, int statu2, int value)
	{
		CBFS::PushFront(statu1 * m_iStatuCount2 + statu2, value);
	}
	int Get(int statu1, int statu2)
	{
		return CBFS::Get(statu1 * m_iStatuCount2 + statu2);
	}
private:
	const int m_iStatuCount2;
};

class CBFS3 : protected CBFS2
{
public:
	CBFS3(int iStatuCount1, int iStatuCount2, int iStatuCount3,int iInit = -1) :CBFS2(iStatuCount1, iStatuCount2* iStatuCount3, iInit), m_iStatuCount3(iStatuCount3)
	{

	}
	bool Peek(int& statu1, int& statu2,int& statu3 )
	{
		int statu23;
		if (!CBFS2::Peek(statu1,statu23))
		{
			return false;
		}
		statu2 = statu23 / m_iStatuCount3;
		statu3 = statu23 % m_iStatuCount3;
		return true;
	}
	void PushBack(int statu1, int statu2,int statu3, int value)
	{
		CBFS2::PushBack(statu1 , statu2*m_iStatuCount3+statu3, value);
	}
	void PushFront(int statu1, int statu2, int statu3, int value)
	{
		CBFS2::PushFront(statu1, statu2 * m_iStatuCount3 + statu3, value);
	}
	int Get(int statu1, int statu2, int statu3)
	{
		return CBFS2::Get(statu1, statu2 * m_iStatuCount3 + statu3);
	}
	const int m_iStatuCount3;
};

class CBFS4 : protected CBFS3
{
public:
	CBFS4(int iStatuCount1, int iStatuCount2, int iStatuCount3,int iStatuCount4, int iInit = -1) :CBFS3(iStatuCount1, iStatuCount2, iStatuCount3* iStatuCount4, iInit), m_iStatuCount4(iStatuCount4)
	{

	}
	bool Peek(int& statu1, int& statu2, int& statu3,int& statu4)
	{
		int statu34;
		if (!CBFS3::Peek(statu1, statu2,statu34))
		{
			return false;
		}
		statu3 = statu34 / m_iStatuCount4;
		statu4 = statu34 % m_iStatuCount4;
		return true;
	}
	void PushBack(int statu1, int statu2, int statu3,int statu4, int value)
	{
		CBFS3::PushBack(statu1, statu2 , statu3* m_iStatuCount4+ statu4, value);
	}
	void PushFront(int statu1, int statu2, int statu3, int statu4, int value)
	{
		CBFS3::PushFront(statu1, statu2, statu3 * m_iStatuCount4 + statu4, value);
	}
	int Get(int statu1, int statu2, int statu3, int statu4)
	{
		return CBFS3::Get(statu1, statu2, statu3 * m_iStatuCount4 + statu4);
	}
	const int m_iStatuCount4;
};

template<class T>
class CEnumGrid
{
public:
	static  void EnumGrid(const vector<vector<T>>& grid,std::function<void(int,int,T)> call )
	{
		for (int r = 0; r < grid.size(); r++)
		{
			for (int c = 0; c < grid.front().size(); c++)
			{
				call(r, c, grid[r][c]);
			}
		}
	}
};
class Solution {
public:
	int minPushBox(vector<vector<char>>& grid) {
		m_r = grid.size();
		m_c = grid[0].size();
		int move[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
		auto CanMove = [&grid](int r, int c)
		{
			if ((r < 0) || (r >= grid.size()))
			{
				return false;
			}
			if ((c < 0) || (c >= grid[0].size()))
			{
				return false;
			}
			return '#' != grid[r][c];
		};
		int sr, sc, br, bc,tr,tc;
		CEnumGrid<char>::EnumGrid(grid, [&](int r, int c, char ch)
			{
				if ('B' == ch)
				{
					br = r;
					bc = c;
				}
				if ('S' == ch)
				{
					sr = r;
					sc = c;
				}
				if ('T' == ch)
				{
					tr = r;
					tc = c;
				}
			});
		CBFS4 bfs(m_r, m_c, m_r, m_c);
		bfs.PushBack(sr, sc, br, bc, 0);
		int r1, c1, r2, c2;
		while (bfs.Peek(r1, c1, r2, c2))
		{
			const int dis = bfs.Get(r1, c1, r2, c2);
			if ((r2 == tr) && (c2 == tc))
			{
				return dis;
			}
			for (const auto& [mr,mc] : move)
			{
				auto r3 = r1 + mr;
				auto c3 = c1 + mc;
				if (!CanMove(r3, c3))
				{
					continue;
				}
				if ((r3 == r2) && (c3 == c2))
				{//必须移动箱子
					auto r4 = r3 + mr;
					auto c4 = c3 + mc;
					if (!CanMove(r4, c4))
					{
						continue;
					}
					bfs.PushBack(r3, c3, r4, c4, dis + 1);
				}
				else
				{
					bfs.PushFront(r3, c3, r2, c2, dis );
				}
			}
		}
		return -1;
	}
	int m_r, m_c;
};
  • 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
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236

测试用例


template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<vector<char>> grid;
	
	{
		Solution sln;
		grid = { {'#','#','#','#','#','#'},
			 {'#','T','#','#','#','#'},
			 {'#','.','.','B','.','#'},
			 {'#','.','#','#','.','#'},
			 {'#','.','.','.','S','#'},
			 {'#','#','#','#','#','#'} };
		auto res = sln.minPushBox(grid);
		Assert(3, res);
	}
	{
		Solution sln;
		grid = { {'#','#','#','#','#','#'},
			 {'#','T','.','.','#','#'},
			 {'#','.','#','B','.','#'},
			 {'#','.','.','.','.','#'},
			 {'#','.','.','.','S','#'},
			 {'#','#','#','#','#','#'} };
		auto res = sln.minPushBox(grid);
		Assert(5, res);
	}
}
  • 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

想法而已，过于复杂：割点、并集查找

状态：箱子所在行列，人所在方位（上右下左） 。
箱子右移的条件：
人能移到箱子左边，箱子能右移（右边没出界，不是墙）
人可能被箱子阻拦：
{ 如果没箱子，人无法到达 无法到达。 e l s e 箱子不是割点 能到达 e l s e 是割点，源点和目标点到时间戳都大于（小于）割点时间戳 能到达。 o t h e r 不能到达。 {如果没箱子，人无法到达无法到达。else箱子不是割点能到达else是割点，源点和目标点到时间戳都大于（小于）割点时间戳能到达。other不能到达。

⎩ ⎨ ⎧​如果没箱子，人无法到达else箱子不是割点else是割点，源点和目标点到时间戳都大于（小于）割点时间戳other​无法到达。能到达能到达。不能到达。​

写了下代码，太复杂了。
错误原因：源点和目标点到时间戳都大于（小于）割点时间戳则能到达是错误的。因为：割点可能被多次访问，所以需要记录割点所有的时间戳，在同一个时间段的可以访问。但这要修改割点函数。抱着一根筋精神，改进了割点函数。

代码

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 CUnionFindMST
{
public:
	CUnionFindMST(const int iNodeSize) :m_uf(iNodeSize)
	{

	}
	void AddEdge(const int iNode1, const int iNode2, int iWeight)
	{
		if (m_uf.IsConnect(iNode1, iNode2))
		{
			return;
		}
		m_iMST += iWeight;
		m_uf.Union(iNode1, iNode2);
	}
	void AddEdge(const vector<int>& v)
	{
		AddEdge(v[0], v[1], v[2]);
	}
	int MST()
	{
		if (m_uf.GetConnetRegionCount() > 1)
		{
			return -1;
		}
		return m_iMST;
	}
private:
	int m_iMST = 0;
	CUnionFind m_uf;
};

class CUnionFindDirect
{
public:
	CUnionFindDirect(int iSize)
	{
		m_vRoot.resize(iSize);
		iota(m_vRoot.begin(), m_vRoot.end(), 0);
	}
	void Connect(bool& bConflic, bool& bCyc, int iFrom, int iTo)
	{
		bConflic = bCyc = false;
		if (iFrom != m_vRoot[iFrom])
		{
			bConflic = true;
		}

		Fresh(iTo);
		if (m_vRoot[iTo] == iFrom)
		{
			bCyc = true;
		}
		if (bConflic || bCyc)
		{
			return;
		}

		m_vRoot[iFrom] = m_vRoot[iTo];
	}
	int GetMaxDest(int iFrom)
	{
		Fresh(iFrom);
		return m_vRoot[iFrom];
	}	
private:
	int Fresh(int iNode)
	{
		if (m_vRoot[iNode] == iNode)
		{
			return iNode;
		}
		return m_vRoot[iNode] = Fresh(m_vRoot[iNode]);
	}
	vector<int> m_vRoot;
};

class CNearestMST
{
public:
	CNearestMST(const int iNodeSize) :m_bDo(iNodeSize), m_vDis(iNodeSize, INT_MAX), m_vNeiTable(iNodeSize)
	{

	}
	void Init(const vector<vector<int>>& edges)
	{
		for (const auto& v : edges)
		{
			Add(v);
		}
	}
	void Add(const vector<int>& v)
	{
		m_vNeiTable[v[0]].emplace_back(v[1], v[2]);
		m_vNeiTable[v[1]].emplace_back(v[0], v[2]);
	}
	int MST(int start)
	{
		int next = start;
		while ((next = AddNode(next)) >= 0);
		return m_iMST;
	}
	int MST(int iNode1, int iNode2, int iWeight)
	{
		m_bDo[iNode1] = true;
		for (const auto& it : m_vNeiTable[iNode1])
		{
			if (m_bDo[it.first])
			{
				continue;
			}
			m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
		}
		m_iMST = iWeight;

		int next = iNode2;
		while ((next = AddNode(next)) >= 0);
		return m_iMST;
	}

private:
	int AddNode(int iCur)
	{
		m_bDo[iCur] = true;
		for (const auto& it : m_vNeiTable[iCur])
		{
			if (m_bDo[it.first])
			{
				continue;
			}
			m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
		}

		int iMinIndex = -1;
		for (int i = 0; i < m_vDis.size(); i++)
		{
			if (m_bDo[i])
			{
				continue;
			}
			if ((-1 == iMinIndex) || (m_vDis[i] < m_vDis[iMinIndex]))
			{
				iMinIndex = i;
			}
		}
		if (-1 != iMinIndex)
		{
			if (INT_MAX == m_vDis[iMinIndex])
			{
				m_iMST = -1;
				return -1;
			}
			m_iMST += m_vDis[iMinIndex];
		}

		return iMinIndex;
	}
	vector<bool> m_bDo;
	vector<long long> m_vDis;
	vector < vector<std::pair<int, int>>> m_vNeiTable;
	long long m_iMST = 0;
};

class CBFSDis
{
public:
	CBFSDis(vector<vector<int>>& vNeiB, vector<int> start)
	{
		m_vDis.assign(vNeiB.size(), m_iNotMayDis);
		queue<int> que;
		for (const auto& n : start)
		{
			m_vDis[n] = 0;
			que.emplace(n);
		}
		while (que.size())
		{
			const int cur = que.front();
			que.pop();
			for (const auto next : vNeiB[cur])
			{
				if (m_iNotMayDis != m_vDis[next])
				{
					continue;
				}
				m_vDis[next] = m_vDis[cur] + 1;
				que.emplace(next);
			}
		}
	}
public:
	const int m_iNotMayDis = 1e9;
	vector<int> m_vDis;
};

class C01BFSDis
{
public:
	C01BFSDis(vector<vector<int>>& vNeiB0, vector<vector<int>>& vNeiB1, int s)
	{
		m_vDis.assign(vNeiB0.size(), -1);
		std::deque<std::pair<int, int>> que;
		que.emplace_back(s, 0);
		while (que.size())
		{
			auto it = que.front();
			const int cur = it.first;
			const int dis = it.second;
			que.pop_front();
			if (-1 != m_vDis[cur])
			{
				continue;
			}
			m_vDis[cur] = it.second;
			for (const auto next : vNeiB0[cur])
			{
				if (-1 != m_vDis[next])
				{
					continue;
				}
				que.emplace_front(next, dis);

			}

			for (const auto next : vNeiB1[cur])
			{
				if (-1 != m_vDis[next])
				{
					continue;
				}
				que.emplace_back(next, dis + 1);
			}
		}
	}
public:
	vector<int> m_vDis;
};
//堆（优先队列)优化迪杰斯特拉算法 狄克斯特拉(Dijkstra)算法详解
typedef pair<long long, int> PAIRLLI;
class  CHeapDis
{
public:
	CHeapDis(int n)
	{
		m_vDis.assign(n, -1);
	}
	void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
	{
		std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap;
		minHeap.emplace(0, start);
		while (minHeap.size())
		{
			const long long llDist = minHeap.top().first;
			const int iCur = minHeap.top().second;
			minHeap.pop();
			if (-1 != m_vDis[iCur])
			{
				continue;
			}
			m_vDis[iCur] = llDist;
			for (const auto& it : vNeiB[iCur])
			{
				minHeap.emplace(llDist + it.second, it.first);
			}
		}
	}
	vector<long long> m_vDis;
};


//朴素迪杰斯特拉算法
class CN2Dis
{
public:
	CN2Dis(int iSize) :m_iSize(iSize), DIS(m_vDis), PRE(m_vPre)
	{

	}
	void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
	{
		m_vDis.assign(m_iSize, -1);
		m_vPre.assign(m_iSize, -1);
		vector<bool> vDo(m_iSize);//点是否已处理
		auto AddNode = [&](int iNode)
		{
			//const int iPreNode = m_vPre[iNode];
			long long llPreDis = m_vDis[iNode];

			vDo[iNode] = true;
			for (const auto& it : vNeiB[iNode])
			{
				if (vDo[it.first])
				{
					continue;
				}

				if ((-1 == m_vDis[it.first]) || (it.second + llPreDis < m_vDis[it.first]))
				{
					m_vDis[it.first] = it.second + llPreDis;
					m_vPre[it.first] = iNode;
				}
			}

			long long llMinDis = LLONG_MAX;
			int iMinIndex = -1;
			for (int i = 0; i < m_vDis.size(); i++)
			{
				if (vDo[i])
				{
					continue;
				}
				if (-1 == m_vDis[i])
				{
					continue;
				}
				if (m_vDis[i] < llMinDis)
				{
					iMinIndex = i;
					llMinDis = m_vDis[i];
				}
			}
			return (LLONG_MAX == llMinDis) ? -1 : iMinIndex;
		};

		int next = start;
		m_vDis[start] = 0;
		while (-1 != (next = AddNode(next)));
	}
	void Cal(int start, const vector<vector<int>>& mat)
	{
		m_vDis.assign(m_iSize, LLONG_MAX);
		m_vPre.assign(m_iSize, -1);
		vector<bool> vDo(m_iSize);//点是否已处理
		auto AddNode = [&](int iNode)
		{
			long long llPreDis = m_vDis[iNode];
			vDo[iNode] = true;
			for (int i = 0; i < m_iSize; i++)
			{
				if (vDo[i])
				{
					continue;
				}
				const long long llCurDis = mat[iNode][i];
				if (llCurDis <= 0)
				{
					continue;
				}
				m_vDis[i] = min(m_vDis[i], m_vDis[iNode] + llCurDis);
			}
			long long llMinDis = LLONG_MAX;
			int iMinIndex = -1;
			for (int i = 0; i < m_iSize; i++)
			{
				if (vDo[i])
				{
					continue;
				}
				if (m_vDis[i] < llMinDis)
				{
					iMinIndex = i;
					llMinDis = m_vDis[i];
				}
			}
			if (LLONG_MAX == llMinDis)
			{
				return -1;
			}

			m_vPre[iMinIndex] = iNode;
			return iMinIndex;
		};

		int next = start;
		m_vDis[start] = 0;
		while (-1 != (next = AddNode(next)));
	}
	const vector<long long>& DIS;
	const vector<int>& PRE;
private:
	const int m_iSize;
	vector<long long> m_vDis;//各点到起点的最短距离
	vector<int>  m_vPre;//最短路径的前一点
};

//多源码路径
template<class T, T INF = 1000 * 1000 * 1000>
class CFloyd
{
public:
	CFloyd(const  vector<vector<T>>& mat)
	{
		m_vMat = mat;
		const int n = mat.size();
		for (int i = 0; i < n; i++)
		{//通过i中转
			for (int i1 = 0; i1 < n; i1++)
			{
				for (int i2 = 0; i2 < n; i2++)
				{
					//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
					m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
					//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
				}
			}
		}
	};
	vector<vector<T>> m_vMat;
};

class CParentToNeiBo
{
public:
	CParentToNeiBo(const vector<int>& parents)
	{
		m_vNeiBo.resize(parents.size());
		for (int i = 0; i < parents.size(); i++)
		{
			if (-1 == parents[i])
			{
				m_root = i;
			}
			else
			{
				m_vNeiBo[parents[i]].emplace_back(i);
			}
		}
	}
	vector<vector<int>> m_vNeiBo;
	int m_root = -1;
};

class CNeiBo2
{
public:
	CNeiBo2(int n, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
	{
		m_vNeiB.resize(n);
	}
	CNeiBo2(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
	{
		m_vNeiB.resize(n);
		for (const auto& v : edges)
		{
			m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
	}
	inline void Add(int iNode1, int iNode2)
	{
		iNode1 -= m_iBase;
		iNode2 -= m_iBase;
		m_vNeiB[iNode1].emplace_back(iNode2);
		if (!m_bDirect)
		{
			m_vNeiB[iNode2].emplace_back(iNode1);
		}
	}
	const int m_iN;
	const bool m_bDirect;
	const int m_iBase;
	vector<vector<int>> m_vNeiB;
};

class CNeiBo3
{
public:
	CNeiBo3(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		m_vNeiB.resize(n);
		AddEdges(edges, bDirect, iBase);
	}
	CNeiBo3(int n)
	{
		m_vNeiB.resize(n);
	}
	void AddEdges(vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		for (const auto& v : edges)
		{
			m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
	}
	vector<vector<std::pair<int, int>>> m_vNeiB;
};


template<class T, T INF = 1000 * 1000 * 1000>
class CNeiBoToMat
{
public:
	CNeiBoToMat(int n, const vector<vector<int>>& edges, bool bDirect = false, bool b1Base = false)
	{
		m_vMat.assign(n, vector<int>(n, INF));
		for (int i = 0; i < n; i++)
		{
			m_vMat[i][i] = 0;
		}
		for (const auto& v : edges)
		{
			m_vMat[v[0] - b1Base][v[1] - b1Base] = v[2];
			if (!bDirect)
			{
				m_vMat[v[1] - b1Base][v[0] - b1Base] = v[2];
			}
		}
	}
	vector<vector<int>> m_vMat;
};
class CCutEdge
{
public:
	CCutEdge(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
	{
		m_vTime.assign(m_iSize, -1);
		m_vCutEdges.resize(m_iSize);
		for (int i = 0; i < m_iSize; i++)
		{
			if (-1 != m_vTime[i])
			{
				continue;
			}
			m_iRegionCount++;
			dfs(i, -1, vNeiB);
		}
	}
	bool IsCut(int node1, int node2)
	{
		return m_vCutEdges[node1].count(node2);
	}
	bool IsCut(int node)
	{
		return m_vCutEdges[node].size();
	}
	int RegionCount()const
	{
		return m_iRegionCount;
	}
protected:
	int dfs(int cur, int parent, const vector<vector<int>>& vNeiB)
	{
		auto& curTime = m_vTime[cur];
		curTime = m_iTime++;
		int iRet = curTime;
		for (const auto& next : vNeiB[cur])
		{
			if (next == parent)
			{
				continue;
			}
			if (-1 != m_vTime[next])
			{
				iRet = min(iRet, m_vTime[next]);
				continue;
			}
			int iNextTime = dfs(next, cur, vNeiB);
			if (iNextTime > curTime)
			{
				m_vCutEdges[cur].emplace(next);
			}
			iRet = min(iRet, iNextTime);
		}
		return iRet;
	}
	vector<int> m_vTime;
	int m_iTime = 0;
	int m_iRegionCount = 0;
	vector<std::unordered_set<int>> m_vCutEdges;
	const int m_iSize;
};

//割点
class CCutPoint
{
public:
	CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
	{
		m_vTime.assign(m_iSize, -1);
		m_vVisitMin.assign(m_iSize, -1);
		for (int i = 0; i < m_iSize; i++)
		{
			if (-1 != m_vTime[i])
			{
				continue;
			}
			m_iRegionCount++;
			dfs(i, -1, vNeiB);
		}
	}
	int RegionCount()const
	{
		return m_iRegionCount;
	}
	const vector<int>& CutPoints()const
	{
		return m_vCutPoints;
	}
	const vector<int>& Tinme()const { return m_vTime; }
protected:
	void dfs(int cur, int parent, const vector<vector<int>>& vNeiB)
	{
		auto& curTime = m_vTime[cur];
		auto& visitMin = m_vVisitMin[cur];
		curTime = m_iTime++;
		visitMin = curTime;
		int iMax = -1;
		int iChildNum = 0;
		for (const auto& next : vNeiB[cur])
		{
			if (next == parent)
			{
				continue;
			}
			if (-1 != m_vTime[next])
			{
				visitMin = min(visitMin, m_vTime[next]);
				continue;
			}
			iChildNum++;
			dfs(next, cur, vNeiB);
			visitMin = min(visitMin, m_vVisitMin[next]);
			iMax = max(iMax, m_vVisitMin[next]);
		}
		if (-1 == parent)
		{
			if (iChildNum >= 2)
			{
				m_vCutPoints.emplace_back(cur);
			}
		}
		else
		{
			if (iMax >= curTime)
			{
				m_vCutPoints.emplace_back(cur);
			}
		}
	}
	vector<int> m_vTime;//各节点到达时间，从0开始。 -1表示未处理
	vector<int> m_vVisitMin;// 
	int m_iTime = 0;
	int m_iRegionCount = 0;
	vector<int> m_vCutPoints;
	const int m_iSize;
};

class CTopSort
{
public:
	//vBackNeiBo[1] = {2} 表示 1完成后，才能完成2
	template<class T >
	void Init(vector<T>& vPreToNext)
	{
		m_c = vPreToNext.size();
		vector<int> vInDeg(m_c);
		for (int cur = 0; cur < m_c; cur++)
		{
			for (const auto& next : vPreToNext[cur])
			{
				vInDeg[next]++;
			}
		}
		queue<int> que;
		for (int i = 0; i < m_c; i++)
		{
			if (0 == vInDeg[i])
			{
				que.emplace(i);
				m_vLeaf.emplace_back(i);
				OnDo(-1, i);
			}
		}

		while (que.size())
		{
			const int cur = que.front();
			que.pop();
			for (const auto& next : vPreToNext[cur])
			{
				vInDeg[next]--;
				if (0 == vInDeg[next])
				{
					que.emplace(next);
					OnDo(cur, next);
				}
			}
		};
	}
	virtual void OnDo(int pre, int cur) = 0;
	int m_c;
	vector<int> m_vLeaf;
};


struct CVec
{
	int r;
	int c;
};
struct CPos
{	
	int r = 0, c = 0;
	int ToMask()const { return s_MaxC * r + c; };
	bool operator==(const CPos& o)const
	{
		return (r == o.r) && (c == o.c);
	}
	CPos operator+(const CVec& v)const
	{
		return { r + v.r, c + v.c };
	}
	CPos operator-(const CVec& v)const
	{
		return{ r - v.r, c - v.c };
	}
	CVec operator-(const CPos& o)const
	{
		return {r - o.r,c- o.c};
	}
	inline static  int s_MaxC = 10'000;
};

class CRange
{
public:
	CRange(int rCount, int cCount, std::function<bool(int, int)> funVilidCur):m_r(rCount),m_c(cCount), m_funVilidCur(funVilidCur)
	{

	}
	bool Vilid(CPos pos)const
	{
		return (pos.r >= 0) && (pos.r < m_r) && (pos.c >= 0) && (pos.c < m_c) && m_funVilidCur(pos.r, pos.c);
	}
	const int m_r, m_c;
protected:
	std::function<bool(int, int)> m_funVilidCur;
};
class  CGridToNeiBo
{
public:
	static vector<vector<int>> ToNeiBo(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount*preR+preC].emplace_back(r*cCount+ c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		return vNeiBo;
	}
};

template<class T = int>
class CEnumGrid
{
public:	
	static  void EnumGrid(vector<vector<T>>& grid, std::function<void(int, int, T&)> call)
	{
		for (int r = 0; r < grid.size(); r++)
		{
			for (int c = 0; c < grid.front().size(); c++)
			{
				call(r, c, grid[r][c]);
			}
		}
	}
	static  void EnumPos(vector<vector<T>>& grid, vector<tuple<T, CPos&>> vRes)
	{
		EnumGrid(grid, [&vRes](int curR, int curC, T& curV)
			{
				for (auto& [value, pos] : vRes)
				{
					if (curV == value)
					{
						pos = { curR,curC };
					}
				}
			});
	}
	inline static const CVec s_Move4[4] = { {1,0},{0,1},{-1,0},{0,-1} };//上右下左
	enum {UP=0,RIGHT,DOWN,LEFT};
};

class CEnumGridEdge
{
public:
	CEnumGridEdge(int r, int c, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext) :m_r(r), m_c(c)
	{
		m_funVilidCur = funVilidCur;
		m_funVilidNext = funVilidNext;
		m_vNext.assign(m_r, vector < vector<pair<int, int>>>(m_c));
		Init();
	}
	vector<vector<int>> BFS(vector<pair<int, int>> start, const int endr = -1, const int endc = -1)
	{
		vector<vector<int>> vDis(m_r, vector<int>(m_c, -1));
		queue<pair<int, int>> que;
		for (const auto& [r, c] : start)
		{
			vDis[r][c] = 0;
			que.emplace(make_pair(r, c));
		}
		while (que.size())
		{
			const auto [r, c] = que.front();
			que.pop();
			for (const auto [nr, nc] : m_vNext[r][c])
			{
				if (-1 != vDis[nr][nc])
				{
					continue;
				}
				vDis[nr][nc] = vDis[r][c] + 1;
				if ((endr == nr) && (endc == nc))
				{
					break;
				}
				que.emplace(make_pair(nr, nc));
			}
		}
		return vDis;
	}
	const int m_r, m_c;
	vector < vector < vector<pair<int, int>>>> m_vNext;
protected:
	void Init()
	{
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
	}
	void Move(int preR, int preC, int r, int c)
	{
		if ((r < 0) || (r >= m_r))
		{
			return;
		}
		if ((c < 0) || (c >= m_c))

		{
			return;
		}
		if (m_funVilidCur(preR, preC) && m_funVilidNext(r, c))
		{
			m_vNext[preR][preC].emplace_back(r, c);
		}
	};
	std::function<bool(int, int)> m_funVilidCur, m_funVilidNext;
};

class CBFS
{
public:
	CBFS(int iStatuCount, int iInit = -1) :m_iStatuCount(iStatuCount), m_iInit(iInit)
	{
		m_res.assign(iStatuCount, iInit);
	}
	bool Peek(int& statu)
	{
		if (m_que.empty())
		{
			return false;
		}
		statu = m_que.front();
		m_que.pop_front();
		return true;
	}
	void PushBack(int statu, int value)
	{
		if (m_iInit != m_res[statu])
		{
			return;
		}
		m_res[statu] = value;
		m_que.push_back(statu);
	}
	void PushFront(int statu, int value)
	{
		if (m_iInit != m_res[statu])
		{
			return;
		}
		m_res[statu] = value;
		m_que.push_front(statu);
	}
	int Get(int statu)
	{
		return m_res[statu];
	}
private:
	const int m_iStatuCount;
	const int m_iInit;
	deque<int> m_que;
	vector<int> m_res;
};

class CBFS2 : protected CBFS
{
public:
	CBFS2(int iStatuCount1, int iStatuCount2, int iInit = -1) :CBFS(iStatuCount1* iStatuCount2, iInit), m_iStatuCount2(iStatuCount2)
	{

	}
	bool Peek(int& statu1, int& statu2)
	{
		int statu;
		if (!CBFS::Peek(statu))
		{
			return false;
		}
		statu1 = statu / m_iStatuCount2;
		statu2 = statu % m_iStatuCount2;
		return true;
	}
	void PushBack(int statu1, int statu2, int value)
	{
		CBFS::PushBack(statu1 * m_iStatuCount2 + statu2, value);
	}
	void PushFront(int statu1, int statu2, int value)
	{
		CBFS::PushFront(statu1 * m_iStatuCount2 + statu2, value);
	}
	int Get(int statu1, int statu2)
	{
		return CBFS::Get(statu1 * m_iStatuCount2 + statu2);
	}
private:
	const int m_iStatuCount2;
};

class CBFS3 : protected CBFS2
{
public:
	CBFS3(int iStatuCount1, int iStatuCount2, int iStatuCount3, int iInit = -1) :CBFS2(iStatuCount1, iStatuCount2* iStatuCount3, iInit), m_iStatuCount3(iStatuCount3)
	{

	}
	bool Peek(int& statu1, int& statu2, int& statu3)
	{
		int statu23;
		if (!CBFS2::Peek(statu1, statu23))
		{
			return false;
		}
		statu2 = statu23 / m_iStatuCount3;
		statu3 = statu23 % m_iStatuCount3;
		return true;
	}
	void PushBack(int statu1, int statu2, int statu3, int value)
	{
		CBFS2::PushBack(statu1, statu2 * m_iStatuCount3 + statu3, value);
	}
	void PushFront(int statu1, int statu2, int statu3, int value)
	{
		CBFS2::PushFront(statu1, statu2 * m_iStatuCount3 + statu3, value);
	}
	int Get(int statu1, int statu2, int statu3)
	{
		return CBFS2::Get(statu1, statu2 * m_iStatuCount3 + statu3);
	}
	const int m_iStatuCount3;
};

class CBFS4 : protected CBFS3
{
public:
	CBFS4(int iStatuCount1, int iStatuCount2, int iStatuCount3, int iStatuCount4, int iInit = -1) :CBFS3(iStatuCount1, iStatuCount2, iStatuCount3* iStatuCount4, iInit), m_iStatuCount4(iStatuCount4)
	{

	}
	bool Peek(int& statu1, int& statu2, int& statu3, int& statu4)
	{
		int statu34;
		if (!CBFS3::Peek(statu1, statu2, statu34))
		{
			return false;
		}
		statu3 = statu34 / m_iStatuCount4;
		statu4 = statu34 % m_iStatuCount4;
		return true;
	}
	void PushBack(int statu1, int statu2, int statu3, int statu4, int value)
	{
		CBFS3::PushBack(statu1, statu2, statu3 * m_iStatuCount4 + statu4, value);
	}
	void PushFront(int statu1, int statu2, int statu3, int statu4, int value)
	{
		CBFS3::PushFront(statu1, statu2, statu3 * m_iStatuCount4 + statu4, value);
	}
	int Get(int statu1, int statu2, int statu3, int statu4)
	{
		return CBFS3::Get(statu1, statu2, statu3 * m_iStatuCount4 + statu4);
	}
	const int m_iStatuCount4;
};


class CCutPointEx
{
public:
	CCutPointEx(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
	{
		m_vTime.assign(m_iSize, -1);	
		m_vCutRegion.resize(m_iSize);
		m_vNodeToRegion.assign(m_iSize,-1);
		m_vCut.assign(m_iSize, false);
		for (int i = 0; i < m_iSize; i++)
		{
			if (-1 != m_vTime[i])
			{
				continue;
			}
			dfs(i, -1, vNeiB);
			m_iRegionCount++;
		}
	}
	bool Visit(int src, int dest, int iCut)
	{
		if (m_vNodeToRegion[src] != m_vNodeToRegion[dest])
		{
			return false;//不在一个连通区域
		}
		if (!m_vCut[iCut])
		{
			return true;
		}
		const int r1 = GetCutRegion(iCut,src);
		const int r2 = GetCutRegion(iCut, dest);
		return r1 == r2;
	}
protected:
	int dfs(int cur, int parent, const vector<vector<int>>& vNeiB)
	{		
		auto& curTime = m_vTime[cur];			
		m_vNodeToRegion[cur] = m_iRegionCount;
		curTime = m_iTime++;		
		int iCutChild=0;
		int iMinTime = curTime;
		for (const auto& next : vNeiB[cur])
		{
			if (next == parent)
			{
				continue;
			}
			if (-1 != m_vTime[next])
			{
				iMinTime = min(iMinTime, m_vTime[next]);
				continue;
			}			
			int iChildBeginTime = m_iTime;
			const int iChildMinTime = dfs(next, cur, vNeiB);
			iMinTime = min(iMinTime, iChildMinTime);
			if (iChildMinTime >= curTime)
			{
				iCutChild++;
				m_vCutRegion[cur].push_back({ iChildBeginTime,m_iTime });
			};
		}
		m_vCut[cur] = (iCutChild + (-1 != parent)) >= 2;
		return iMinTime;
	}	
	int GetCutRegion(int iCut, int iNode)const 
	{
		const auto& v = m_vCutRegion[iCut];
		auto it = std::upper_bound(v.begin(), v.end(), m_vTime[iNode],[](int time, const std::pair<int, int>& pr) {return time < pr.first; });
		if (v.begin() == it)
		{
			return v.size();
		}
		--it;
		return (it->second > m_vTime[iNode]) ? (it - v.begin()) : v.size();
	}
	int m_iTime = 0;	
	const int m_iSize;
	int m_iRegionCount=0;
	vector<int> m_vTime;//各节点到达时间，从0开始。 -1表示未处理
	vector<bool> m_vCut;
	vector<int> m_vNodeToRegion;
	vector<vector<pair<int,int>>> m_vCutRegion;
};

class Solution {
public:
	int minPushBox(vector<vector<char>>& grid) {		
		auto Vilid = [&](int r, int c) {return '#' != grid[r][c]; };
		CRange range(grid.size(), grid.front().size(), Vilid);	
		CPos::s_MaxC = range.m_c;		
		auto neiBo = CGridToNeiBo::ToNeiBo(range.m_r, range.m_c, Vilid, Vilid);		
		CCutPointEx cutPoint(neiBo);
		auto Visit = [&](CPos s, CPos d, CPos b){			
			return range.Vilid(d) && cutPoint.Visit(s.ToMask(),d.ToMask(),b.ToMask());
		};
		CBFS3 bfs(range.m_r, range.m_c, 4);
		CPos sInit,tInit,bInit;
		CEnumGrid<char>::EnumPos(grid, { { 'B',bInit },{'T',tInit},{'S',sInit} });
		auto MovePeo = [&](CPos peo, CPos bCur, int iCurDis)		{
			for (int i = 0; i < 4; i++) {
				if (Visit(peo, bCur + CEnumGrid<>::s_Move4[i], bCur)) {
					bfs.PushFront(bCur.r, bCur.c, i, iCurDis);
				}
			}
		};
		MovePeo(sInit, bInit, 0);
		int br1, bc1, pd;
		while (bfs.Peek(br1, bc1, pd))		{
			CPos bCur = { br1,bc1 };
			CPos peo = bCur + CEnumGrid<>::s_Move4[pd];
			const int CurDis = bfs.Get(br1, bc1, pd);
			if (bCur == tInit )			{
				return CurDis;	}	
			MovePeo(peo, bCur, CurDis);
			auto dest = bCur - CEnumGrid<>::s_Move4[pd];
			if (range.Vilid(dest)){
				bfs.PushBack(dest.r, dest.c, pd, CurDis + 1);
			}
		}			
		return -1;
	}
};
  • 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
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367
  • 368
  • 369
  • 370
  • 371
  • 372
  • 373
  • 374
  • 375
  • 376
  • 377
  • 378
  • 379
  • 380
  • 381
  • 382
  • 383
  • 384
  • 385
  • 386
  • 387
  • 388
  • 389
  • 390
  • 391
  • 392
  • 393
  • 394
  • 395
  • 396
  • 397
  • 398
  • 399
  • 400
  • 401
  • 402
  • 403
  • 404
  • 405
  • 406
  • 407
  • 408
  • 409
  • 410
  • 411
  • 412
  • 413
  • 414
  • 415
  • 416
  • 417
  • 418
  • 419
  • 420
  • 421
  • 422
  • 423
  • 424
  • 425
  • 426
  • 427
  • 428
  • 429
  • 430
  • 431
  • 432
  • 433
  • 434
  • 435
  • 436
  • 437
  • 438
  • 439
  • 440
  • 441
  • 442
  • 443
  • 444
  • 445
  • 446
  • 447
  • 448
  • 449
  • 450
  • 451
  • 452
  • 453
  • 454
  • 455
  • 456
  • 457
  • 458
  • 459
  • 460
  • 461
  • 462
  • 463
  • 464
  • 465
  • 466
  • 467
  • 468
  • 469
  • 470
  • 471
  • 472
  • 473
  • 474
  • 475
  • 476
  • 477
  • 478
  • 479
  • 480
  • 481
  • 482
  • 483
  • 484
  • 485
  • 486
  • 487
  • 488
  • 489
  • 490
  • 491
  • 492
  • 493
  • 494
  • 495
  • 496
  • 497
  • 498
  • 499
  • 500
  • 501
  • 502
  • 503
  • 504
  • 505
  • 506
  • 507
  • 508
  • 509
  • 510
  • 511
  • 512
  • 513
  • 514
  • 515
  • 516
  • 517
  • 518
  • 519
  • 520
  • 521
  • 522
  • 523
  • 524
  • 525
  • 526
  • 527
  • 528
  • 529
  • 530
  • 531
  • 532
  • 533
  • 534
  • 535
  • 536
  • 537
  • 538
  • 539
  • 540
  • 541
  • 542
  • 543
  • 544
  • 545
  • 546
  • 547
  • 548
  • 549
  • 550
  • 551
  • 552
  • 553
  • 554
  • 555
  • 556
  • 557
  • 558
  • 559
  • 560
  • 561
  • 562
  • 563
  • 564
  • 565
  • 566
  • 567
  • 568
  • 569
  • 570
  • 571
  • 572
  • 573
  • 574
  • 575
  • 576
  • 577
  • 578
  • 579
  • 580
  • 581
  • 582
  • 583
  • 584
  • 585
  • 586
  • 587
  • 588
  • 589
  • 590
  • 591
  • 592
  • 593
  • 594
  • 595
  • 596
  • 597
  • 598
  • 599
  • 600
  • 601
  • 602
  • 603
  • 604
  • 605
  • 606
  • 607
  • 608
  • 609
  • 610
  • 611
  • 612
  • 613
  • 614
  • 615
  • 616
  • 617
  • 618
  • 619
  • 620
  • 621
  • 622
  • 623
  • 624
  • 625
  • 626
  • 627
  • 628
  • 629
  • 630
  • 631
  • 632
  • 633
  • 634
  • 635
  • 636
  • 637
  • 638
  • 639
  • 640
  • 641
  • 642
  • 643
  • 644
  • 645
  • 646
  • 647
  • 648
  • 649
  • 650
  • 651
  • 652
  • 653
  • 654
  • 655
  • 656
  • 657
  • 658
  • 659
  • 660
  • 661
  • 662
  • 663
  • 664
  • 665
  • 666
  • 667
  • 668
  • 669
  • 670
  • 671
  • 672
  • 673
  • 674
  • 675
  • 676
  • 677
  • 678
  • 679
  • 680
  • 681
  • 682
  • 683
  • 684
  • 685
  • 686
  • 687
  • 688
  • 689
  • 690
  • 691
  • 692
  • 693
  • 694
  • 695
  • 696
  • 697
  • 698
  • 699
  • 700
  • 701
  • 702
  • 703
  • 704
  • 705
  • 706
  • 707
  • 708
  • 709
  • 710
  • 711
  • 712
  • 713
  • 714
  • 715
  • 716
  • 717
  • 718
  • 719
  • 720
  • 721
  • 722
  • 723
  • 724
  • 725
  • 726
  • 727
  • 728
  • 729
  • 730
  • 731
  • 732
  • 733
  • 734
  • 735
  • 736
  • 737
  • 738
  • 739
  • 740
  • 741
  • 742
  • 743
  • 744
  • 745
  • 746
  • 747
  • 748
  • 749
  • 750
  • 751
  • 752
  • 753
  • 754
  • 755
  • 756
  • 757
  • 758
  • 759
  • 760
  • 761
  • 762
  • 763
  • 764
  • 765
  • 766
  • 767
  • 768
  • 769
  • 770
  • 771
  • 772
  • 773
  • 774
  • 775
  • 776
  • 777
  • 778
  • 779
  • 780
  • 781
  • 782
  • 783
  • 784
  • 785
  • 786
  • 787
  • 788
  • 789
  • 790
  • 791
  • 792
  • 793
  • 794
  • 795
  • 796
  • 797
  • 798
  • 799
  • 800
  • 801
  • 802
  • 803
  • 804
  • 805
  • 806
  • 807
  • 808
  • 809
  • 810
  • 811
  • 812
  • 813
  • 814
  • 815
  • 816
  • 817
  • 818
  • 819
  • 820
  • 821
  • 822
  • 823
  • 824
  • 825
  • 826
  • 827
  • 828
  • 829
  • 830
  • 831
  • 832
  • 833
  • 834
  • 835
  • 836
  • 837
  • 838
  • 839
  • 840
  • 841
  • 842
  • 843
  • 844
  • 845
  • 846
  • 847
  • 848
  • 849
  • 850
  • 851
  • 852
  • 853
  • 854
  • 855
  • 856
  • 857
  • 858
  • 859
  • 860
  • 861
  • 862
  • 863
  • 864
  • 865
  • 866
  • 867
  • 868
  • 869
  • 870
  • 871
  • 872
  • 873
  • 874
  • 875
  • 876
  • 877
  • 878
  • 879
  • 880
  • 881
  • 882
  • 883
  • 884
  • 885
  • 886
  • 887
  • 888
  • 889
  • 890
  • 891
  • 892
  • 893
  • 894
  • 895
  • 896
  • 897
  • 898
  • 899
  • 900
  • 901
  • 902
  • 903
  • 904
  • 905
  • 906
  • 907
  • 908
  • 909
  • 910
  • 911
  • 912
  • 913
  • 914
  • 915
  • 916
  • 917
  • 918
  • 919
  • 920
  • 921
  • 922
  • 923
  • 924
  • 925
  • 926
  • 927
  • 928
  • 929
  • 930
  • 931
  • 932
  • 933
  • 934
  • 935
  • 936
  • 937
  • 938
  • 939
  • 940
  • 941
  • 942
  • 943
  • 944
  • 945
  • 946
  • 947
  • 948
  • 949
  • 950
  • 951
  • 952
  • 953
  • 954
  • 955
  • 956
  • 957
  • 958
  • 959
  • 960
  • 961
  • 962
  • 963
  • 964
  • 965
  • 966
  • 967
  • 968
  • 969
  • 970
  • 971
  • 972
  • 973
  • 974
  • 975
  • 976
  • 977
  • 978
  • 979
  • 980
  • 981
  • 982
  • 983
  • 984
  • 985
  • 986
  • 987
  • 988
  • 989
  • 990
  • 991
  • 992
  • 993
  • 994
  • 995
  • 996
  • 997
  • 998
  • 999
  • 1000
  • 1001
  • 1002
  • 1003
  • 1004
  • 1005
  • 1006
  • 1007
  • 1008
  • 1009
  • 1010
  • 1011
  • 1012
  • 1013
  • 1014
  • 1015
  • 1016
  • 1017
  • 1018
  • 1019
  • 1020
  • 1021
  • 1022
  • 1023
  • 1024
  • 1025
  • 1026
  • 1027
  • 1028
  • 1029
  • 1030
  • 1031
  • 1032
  • 1033
  • 1034
  • 1035
  • 1036
  • 1037
  • 1038
  • 1039
  • 1040
  • 1041
  • 1042
  • 1043
  • 1044
  • 1045
  • 1046
  • 1047
  • 1048
  • 1049
  • 1050
  • 1051
  • 1052
  • 1053
  • 1054
  • 1055
  • 1056
  • 1057
  • 1058
  • 1059
  • 1060
  • 1061
  • 1062
  • 1063
  • 1064
  • 1065
  • 1066
  • 1067
  • 1068
  • 1069
  • 1070
  • 1071
  • 1072
  • 1073
  • 1074
  • 1075
  • 1076
  • 1077
  • 1078
  • 1079
  • 1080
  • 1081
  • 1082
  • 1083
  • 1084
  • 1085
  • 1086
  • 1087
  • 1088
  • 1089
  • 1090
  • 1091
  • 1092
  • 1093
  • 1094
  • 1095
  • 1096
  • 1097
  • 1098
  • 1099
  • 1100
  • 1101
  • 1102
  • 1103
  • 1104
  • 1105
  • 1106
  • 1107
  • 1108
  • 1109
  • 1110
  • 1111
  • 1112
  • 1113
  • 1114
  • 1115
  • 1116
  • 1117
  • 1118
  • 1119
  • 1120
  • 1121
  • 1122
  • 1123
  • 1124
  • 1125
  • 1126
  • 1127
  • 1128
  • 1129
  • 1130
  • 1131
  • 1132
  • 1133
  • 1134
  • 1135
  • 1136
  • 1137
  • 1138
  • 1139
  • 1140
  • 1141
  • 1142
  • 1143
  • 1144
  • 1145
  • 1146
  • 1147
  • 1148
  • 1149
  • 1150
  • 1151
  • 1152
  • 1153
  • 1154
  • 1155
  • 1156
  • 1157
  • 1158
  • 1159
  • 1160
  • 1161
  • 1162
  • 1163
  • 1164
  • 1165
  • 1166
  • 1167
  • 1168
  • 1169
  • 1170
  • 1171
  • 1172
  • 1173
  • 1174
  • 1175
  • 1176
  • 1177
  • 1178
  • 1179
  • 1180
  • 1181
  • 1182
  • 1183
  • 1184
  • 1185
  • 1186
  • 1187
  • 1188
  • 1189
  • 1190
  • 1191
  • 1192
  • 1193
  • 1194
  • 1195
  • 1196
  • 1197
  • 1198
  • 1199
  • 1200
  • 1201
  • 1202
  • 1203
  • 1204
  • 1205
  • 1206
  • 1207
  • 1208
  • 1209
  • 1210
  • 1211
  • 1212
  • 1213
  • 1214
  • 1215
  • 1216
  • 1217
  • 1218
  • 1219
  • 1220
  • 1221
  • 1222
  • 1223
  • 1224
  • 1225
  • 1226
  • 1227
  • 1228
  • 1229
  • 1230
  • 1231
  • 1232
  • 1233
  • 1234
  • 1235
  • 1236
  • 1237
  • 1238
  • 1239
  • 1240

2023年4月

class CGridCanVisit
{
public:
CGridCanVisit(const vector& bCanVisit, int r, int c) :m_bCanVisit(bCanVisit), m_r(m_bCanVisit.size()), m_c(m_bCanVisit[0].size())
{
m_vDis.assign(m_r, vector(m_c,INT_MAX/2));
Dist(r, c);
}
bool Vilid(const int r,const int c )
{
if ((r < 0) || (r >= m_r))
{
return false;
}
if ((c < 0) || (c >= m_c))
{
return false;
}
return true;
}
const vector& Dis()const
{
return m_vDis;
}
const vector& m_bCanVisit;
private:
//INT_MAX/2 表示无法到达
void Dist(int r, int c)
{
m_vDis.assign(m_r, vector(m_c, INT_MAX / 2));
vector vHasDo(m_r, vector(m_c));
std::queue> que;
auto Add = [&](const int& r, const int& c, const int& iDis)
{
if (!Vilid(r, c))
{
return;
}
if (vHasDo[r][c])
{
return;
}
if (!m_bCanVisit[r][c])
{
vHasDo[r][c] = true;
return;
}
if (iDis >= m_vDis[r][c])
{
return;
}
que.emplace(r, c);
m_vDis[r][c] = iDis;
vHasDo[r][c] = true;
};
Add(r, c, 0);
while (que.size())
{
const int r = que.front().first;
const int c = que.front().second;
que.pop();
const int iDis = m_vDis[r][c];
Add(r + 1, c, iDis + 1);
Add(r - 1, c, iDis + 1);
Add(r, c + 1, iDis + 1);
Add(r, c - 1, iDis + 1);
}
}
vector m_vDis;
const int m_r;
const int m_c;
};
class Solution {
public:
int minPushBox(vector& grid) {
std::pair pB, pS, pT;
m_r = grid.size();
m_c = grid[0].size();
vector vCanVisit(m_r, vector(m_c));
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
const char ch = grid[r][c];
if (‘S’ == ch)
{
pS = std::make_pair(r, c);
}
else if (‘T’ == ch)
{
pT = std::make_pair(r, c);
}
else if (‘B’ == ch)
{
pB = std::make_pair(r, c);
}
vCanVisit[r][c] = ‘#’ != ch;
}
}
std::unordered_set vHasDo;
std::queue> que;
auto Add = [&](int r, int c, int iSR, int iSC)
{
const int iMask = r * 100 * 100 * 100 + c * 100 * 100 + iSR * 100 + iSC;
if (vHasDo.count(iMask))
{
return;
}
vHasDo.insert(iMask);
que.emplace(r, c, iSR, iSC);
};
auto Move = [&]( CGridCanVisit& gc,int r, int c, int iOldR, int iOldC, int iSR, int iSC)
{
if (!gc.Vilid(r, c))
{
return;//非法行列好
}
if (!gc.m_bCanVisit[r][c])
{//rc是墙无法推动
return;
}
auto vDis = gc.Dis();
const int r2 = iOldR * 2 - r;
const int c2 = iOldC * 2 - c;
if (!gc.Vilid(r2, c2))
{
return;
}
if (vDis[r2][c2] >= 1000 * 1000)
{
return;//人没有地方占，无法推
}
Add(r, c, iOldR, iOldC);
};
std::queue> preQue;
preQue.emplace(pB.first, pB.second, pS.first, pS.second);
for (int i = 0; preQue.size(); i++ )
{
while (preQue.size())
{
auto cur = preQue.front();
if ((get<0>(cur) == pT.first) && (get<1>(cur) == pT.second))
{
return i;
}
preQue.pop();
auto tmp = vCanVisit;
tmp[get<0>(cur)][get<1>(cur)] = false;
CGridCanVisit gc(tmp, get<2>(cur), get<3>(cur));
Move(gc, get<0>(cur)+1, get<1>(cur), get<0>(cur), get<1>(cur), get<2>(cur), get<3>(cur));
Move(gc, get<0>(cur)-1, get<1>(cur), get<0>(cur), get<1>(cur), get<2>(cur), get<3>(cur));
Move(gc, get<0>(cur), get<1>(cur)+1, get<0>(cur), get<1>(cur), get<2>(cur), get<3>(cur));
Move(gc, get<0>(cur), get<1>(cur)-1, get<0>(cur), get<1>(cur), get<2>(cur), get<3>(cur));
}
preQue.swap(que);
}
return -1;
}
int m_r;
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览58439 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/136202491"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！