当前位置：首页 > news >正文

十堰网站建设价格/广州:推动优化防控措施落

news 文章来源：https://blog.csdn.net/he_zhidan/article/details/136202491 2025/3/17 19:14:02

十堰网站建设价格,广州:推动优化防控措施落,wordpress 视频显示图片,企业网站开发要学什么作者推荐视频算法专题涉及知识点广度优先搜索网格割点并集查找 LeetCode:1263. 推箱子「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或…

作者推荐

视频算法专题

涉及知识点

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

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广度优先搜索

状态：箱子所在行列，人所在行列
人试图向上下左右移动。以左移为例。
$\begin{cases} 如果人可以左移，人左移，加到队首 & 箱子不在左边\\ 如果人和箱子都可以左移，人箱子左移，加到队尾 &箱子在人左边\\ \end{cases}$
妙在无需考虑：箱子对人的影响。

代码

核心代码

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;
};

测试用例


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);}
}

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

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

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

代码

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完成后，才能完成2template<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;}
};

2023年4月

class CGridCanVisit
{
public:
CGridCanVisit(const vector<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<vector>& Dis()const
{
return m_vDis;
}
const vector<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<vector> vHasDo(m_r, vector(m_c));
std::queue<std::pair<int, int>> 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<vector> m_vDis;
const int m_r;
const int m_c;
};
class Solution {
public:
int minPushBox(vector<vector>& grid) {
std::pair<int, int> pB, pS, pT;
m_r = grid.size();
m_c = grid[0].size();
vector<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<std::tuple<int, int, int, int>> 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<std::tuple<int, int, int, int>> 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

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

测试环境

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