陕西网站建设陕icp备,WordPress网页小游戏,建设装修网站,如何下载js做的网站作者推荐
视频算法专题
涉及知识点
广度优先搜索 网格 割点 并集查找
LeetCode:1263. 推箱子
「推箱子」是一款风靡全球的益智小游戏#xff0c;玩家需要将箱子推到仓库中的目标位置。 游戏地图用大小为 m x n 的网格 grid 表示#xff0c;其中每个元素可以是墙、地板或…作者推荐
视频算法专题
涉及知识点
广度优先搜索 网格 割点 并集查找
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;dequeint m_que;vectorint 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_iStatuCount3statu3, 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;
};templateclass T
class CEnumGrid
{
public:static void EnumGrid(const vectorvectorT grid,std::functionvoid(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(vectorvectorchar 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;CEnumGridchar::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;
};测试用例 templateclass T,class T2
void Assert(const T t1, const T2 t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{vectorvectorchar 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);}
}
想法而已过于复杂割点、并集查找
状态箱子所在行列人所在方位上右下左 。 箱子右移的条件 人能移到箱子左边箱子能右移右边没出界不是墙 人可能被箱子阻拦 { 如果没箱子人无法到达 无法到达。 e l s e 箱子不是割点 能到达 e l s e 是割点源点和目标点到时间戳都大于小于割点时间戳 能到达。 o t h e r 不能到达。 \begin{cases} 如果没箱子人无法到达 无法到达。\\ else 箱子不是割点 能到达 \\ else 是割点源点和目标点到时间戳都大于小于割点时间戳 能到达。\\ other 不能到达。\\ \end{cases} ⎩ ⎨ ⎧如果没箱子人无法到达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(vectorvectorint 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;}vectorint GetNodeCountOfRegion()//各联通区域的节点数量{const int iNodeSize m_vNodeToRegion.size();vectorint vRet(iNodeSize);for (int i 0; i iNodeSize; i){vRet[GetConnectRegionIndex(i)];}return vRet;}std::unordered_mapint, vectorint GetNodeOfRegion(){std::unordered_mapint, vectorint 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;}vectorint 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 vectorint 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]);}vectorint m_vRoot;
};class CNearestMST
{
public:CNearestMST(const int iNodeSize) :m_bDo(iNodeSize), m_vDis(iNodeSize, INT_MAX), m_vNeiTable(iNodeSize){}void Init(const vectorvectorint edges){for (const auto v : edges){Add(v);}}void Add(const vectorint 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;}vectorbool m_bDo;vectorlong long m_vDis;vector vectorstd::pairint, int m_vNeiTable;long long m_iMST 0;
};class CBFSDis
{
public:CBFSDis(vectorvectorint vNeiB, vectorint start){m_vDis.assign(vNeiB.size(), m_iNotMayDis);queueint 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;vectorint m_vDis;
};class C01BFSDis
{
public:C01BFSDis(vectorvectorint vNeiB0, vectorvectorint vNeiB1, int s){m_vDis.assign(vNeiB0.size(), -1);std::dequestd::pairint, 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:vectorint m_vDis;
};
//堆优先队列)优化迪杰斯特拉算法 狄克斯特拉(Dijkstra)算法详解
typedef pairlong long, int PAIRLLI;
class CHeapDis
{
public:CHeapDis(int n){m_vDis.assign(n, -1);}void Cal(int start, const vectorvectorpairint, int vNeiB){std::priority_queuePAIRLLI, vectorPAIRLLI, greaterPAIRLLI 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);}}}vectorlong long m_vDis;
};//朴素迪杰斯特拉算法
class CN2Dis
{
public:CN2Dis(int iSize) :m_iSize(iSize), DIS(m_vDis), PRE(m_vPre){}void Cal(int start, const vectorvectorpairint, int vNeiB){m_vDis.assign(m_iSize, -1);m_vPre.assign(m_iSize, -1);vectorbool 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 vectorvectorint mat){m_vDis.assign(m_iSize, LLONG_MAX);m_vPre.assign(m_iSize, -1);vectorbool 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 vectorlong long DIS;const vectorint PRE;
private:const int m_iSize;vectorlong long m_vDis;//各点到起点的最短距离vectorint m_vPre;//最短路径的前一点
};//多源码路径
templateclass T, T INF 1000 * 1000 * 1000
class CFloyd
{
public:CFloyd(const vectorvectorT 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]中转的最短距离}}}};vectorvectorT m_vMat;
};class CParentToNeiBo
{
public:CParentToNeiBo(const vectorint 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);}}}vectorvectorint 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, vectorvectorint 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;vectorvectorint m_vNeiB;
};class CNeiBo3
{
public:CNeiBo3(int n, vectorvectorint edges, bool bDirect, int iBase 0){m_vNeiB.resize(n);AddEdges(edges, bDirect, iBase);}CNeiBo3(int n){m_vNeiB.resize(n);}void AddEdges(vectorvectorint 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]);}}}vectorvectorstd::pairint, int m_vNeiB;
};templateclass T, T INF 1000 * 1000 * 1000
class CNeiBoToMat
{
public:CNeiBoToMat(int n, const vectorvectorint edges, bool bDirect false, bool b1Base false){m_vMat.assign(n, vectorint(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];}}}vectorvectorint m_vMat;
};
class CCutEdge
{
public:CCutEdge(const vectorvectorint 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 vectorvectorint 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;}vectorint m_vTime;int m_iTime 0;int m_iRegionCount 0;vectorstd::unordered_setint m_vCutEdges;const int m_iSize;
};//割点
class CCutPoint
{
public:CCutPoint(const vectorvectorint 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 vectorint CutPoints()const{return m_vCutPoints;}const vectorint Tinme()const { return m_vTime; }
protected:void dfs(int cur, int parent, const vectorvectorint 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);}}}vectorint m_vTime;//各节点到达时间从0开始。 -1表示未处理vectorint m_vVisitMin;// int m_iTime 0;int m_iRegionCount 0;vectorint m_vCutPoints;const int m_iSize;
};class CTopSort
{
public://vBackNeiBo[1] {2} 表示 1完成后才能完成2templateclass T void Init(vectorT vPreToNext){m_c vPreToNext.size();vectorint vInDeg(m_c);for (int cur 0; cur m_c; cur){for (const auto next : vPreToNext[cur]){vInDeg[next];}}queueint 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;vectorint 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 10000;
};class CRange
{
public:CRange(int rCount, int cCount, std::functionbool(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::functionbool(int, int) m_funVilidCur;
};
class CGridToNeiBo
{
public:static vectorvectorint ToNeiBo(int rCount, int cCount, std::functionbool(int, int) funVilidCur, std::functionbool(int, int) funVilidNext){vectorvectorint 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*preRpreC].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;}
};templateclass T int
class CEnumGrid
{
public: static void EnumGrid(vectorvectorT grid, std::functionvoid(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(vectorvectorT grid, vectortupleT, 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 {UP0,RIGHT,DOWN,LEFT};
};class CEnumGridEdge
{
public:CEnumGridEdge(int r, int c, std::functionbool(int, int) funVilidCur, std::functionbool(int, int) funVilidNext) :m_r(r), m_c(c){m_funVilidCur funVilidCur;m_funVilidNext funVilidNext;m_vNext.assign(m_r, vector vectorpairint, int(m_c));Init();}vectorvectorint BFS(vectorpairint, int start, const int endr -1, const int endc -1){vectorvectorint vDis(m_r, vectorint(m_c, -1));queuepairint, 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 vectorpairint, 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::functionbool(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;dequeint m_que;vectorint 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 vectorvectorint 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 vectorvectorint vNeiB){ auto curTime m_vTime[cur]; m_vNodeToRegion[cur] m_iRegionCount;curTime m_iTime; int iCutChild0;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::pairint, 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_iRegionCount0;vectorint m_vTime;//各节点到达时间从0开始。 -1表示未处理vectorbool m_vCut;vectorint m_vNodeToRegion;vectorvectorpairint,int m_vCutRegion;
};class Solution {
public:int minPushBox(vectorvectorchar 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;CEnumGridchar::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 vectorvector 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 vectorvector Dis()const { return m_vDis; } const vectorvector m_bCanVisit; private: //INT_MAX/2 表示无法到达 void Dist(int r, int c) { m_vDis.assign(m_r, vector(m_c, INT_MAX / 2)); vectorvector vHasDo(m_r, vector(m_c)); std::queuestd::pairint, 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); } } vectorvector m_vDis; const int m_r; const int m_c; }; class Solution { public: int minPushBox(vectorvector grid) { std::pairint, int pB, pS, pT; m_r grid.size(); m_c grid[0].size(); vectorvector 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::queuestd::tupleint, 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::queuestd::tupleint, 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 ((get0(cur) pT.first) (get1(cur) pT.second)) { return i; } preQue.pop(); auto tmp vCanVisit; tmp[get0(cur)][get1(cur)] false; CGridCanVisit gc(tmp, get2(cur), get3(cur)); Move(gc, get0(cur)1, get1(cur), get0(cur), get1(cur), get2(cur), get3(cur)); Move(gc, get0(cur)-1, get1(cur), get0(cur), get1(cur), get2(cur), get3(cur)); Move(gc, get0(cur), get1(cur)1, get0(cur), get1(cur), get2(cur), get3(cur)); Move(gc, get0(cur), get1(cur)-1, get0(cur), get1(cur), get2(cur), get3(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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
