如何建设销售型企业网站/怎么给自己的公司做网站
作者推荐
视频算法专题
涉及知识点
广度优先搜索 网格 割点 并集查找
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);}
}想法而已，过于复杂：割点、并集查找
状态：箱子所在行列，人所在方位（上右下左） 。
箱子右移的条件：
人能移到箱子左边，箱子能右移（右边没出界，不是墙）
人可能被箱子阻拦：
{ 如果没箱子，人无法到达 无法到达。 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(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
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
相关文章：
【广度优先搜索】【网格】【割点】1263. 推箱子
作者推荐 视频算法专题 涉及知识点 广度优先搜索 网格 割点 并集查找 LeetCode:1263. 推箱子 「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。 游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或…...
论文精读--GPT1
把transformer的解码器拿出来，在没有标号的大量文本数据上训练一个语言模型，来获得预训练模型，然后到子任务上微调，得到每个任务所需的分类器 Abstract Natural language understanding comprises a wide range of diverse tasks…...
C/C++的内存管理（1）
内存管理 C与C的内存分布C语言中动态内存管理方式回顾C内存管理的方式 C与C的内存分布 我们学习C语言时就知道，储存不同的变量计算机会相应分配不同区块的内存。那为什么要把内存化为不同的区域呢？实质上是为了方便管理 下面我们来看看下面一道例题&…...
C 标准库 - ＜stdlib.h＞
简介 <stdlib.h> 头文件定义了四个变量类型、一些宏和各种通用工具函数。 库变量 下面是头文件 stdlib.h 中定义的变量类型： 序号变量 & 描述1size_t2wchar_t3div_t4ldiv_t 库宏 下面是头文件 stdlib.h 中定义的宏： 序号宏 & 描述1…...
Python中回调函数的理解与应用
前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站零基础入门的AI学习网站~。 目录 前言 回调函数的概念 回调函数的基本用法 回调函数的实现方式 1 使用函数 2 使用类方法 3 使用类实…...
抖音数据挖掘软件|视频内容提取
针对用户获取抖音视频的需求，我们开发了一款功能强大的工具，旨在解决用户在获取抖音视频时需要逐个复制链接、下载的繁琐问题。我们希望用户能够通过简单的关键词搜索，实现自动批量抓取视频，并根据需要进行选择性批量下载。因此&a…...
PostgreSQL如何使用UUID
离线安装时，一般有四个包，都安装的话，只需要开启uuid的使用即可，如果工具包(即 postgresql11-contrib）没有安装的话，需要单独安装一次，再进行开启。 开启UUID方法 下面介绍一下如何开启&#…...
网络原理 - HTTP/HTTPS(4)
HTTP响应详解 认识"状态码"(status code) 状态码表示访问一个页面的结果.(是访问成功,还是失败,还是其它的一些情况...).(响应结果如何) 学习状态码 -> 为了调试问题. 写服务器时,按照状态码的含义正确使用. 200 OK 这是最常见的状态码,表示访问成功. 抓包抓…...
Vue+SpringBoot打造在线课程教学系统
目录 一、摘要1.1 系统介绍1.2 项目录屏 二、研究内容2.1 课程类型管理模块2.2 课程管理模块2.3 课时管理模块2.4 课程交互模块2.5 系统基础模块 三、系统设计3.1 用例设计3.2 数据库设计 四、系统展示4.1 管理后台4.2 用户网页 五、样例代码5.1 新增课程类型5.2 网站登录5.3 课…...
数据存储-文件存储
一、CSV文件存储 csv是python的标准库 列表数据写入csv文件 import csvheader [班级, 姓名, 性别, 手机号, QQ] # 二维数组 rows [[学习一班, 大娃, 男, a130111111122, 987456123],[学习二班, 二娃, 女, a130111111123, 987456155],[学习三班, 三娃, 男, a130111111124, …...
【Activiti7】全新Activiti7工作流讲解
一、Activiti7概述 官网地址：https://www.activiti.org/ Activiti由Alfresco软件开发，目前最高版本Activiti 7。是BPMN的一个基于java的软件实现，不过 Activiti 不仅仅包括BPMN，还有DMN决策表和CMMN Case管理引擎，并且有自己的用户管理、微 服务API 等一系列功能，是一…...
C++ 学习(1)---- 左值 右值和右值引用
这里写目录标题 左值右值左值引用和右值引用右值引用和移动构造函数std::move 移动语义返回值优化移动操作要保证安全 万能引用std::forward 完美转发传入左值传入右值 左值 左值是指可以使用 & 符号获取到内存地址的表达式，一般出现在赋值语句的左边ÿ…...
Redis能保证数据不丢失吗？
引言 大家即使没用过Redis，也应该都听说过Redis的威名。 Redis是一种Nosql类型的数据存储，全称Remote Dictionary Server，也就是远程字典服务器，用过Dictionary的应该都知道它是一种键值对（Key-Value）的数…...
C++基础知识（六：继承）
首先我们应该知道C的三大特性就是封装、继承和多态。 此篇文章将详细的讲解继承的作用和使用方法。 继承 一个类，继承另一个已有的类，创建的过程 父类(基类)派生出子类(派生类)的过程 继承提高了代码的复用性 【1】继承的格式 class 类名:父类名 {}; 【…...
RM电控讲义【HAL库篇】（二）
8080并口模式是一种常见的计算机接口模式，主要用于LCD（液晶显示屏）模块。 在8080并口模式中，通信端口包括多种信号线，用于实现数据的读写和控制功能。主要的信号线包括： CS（片选信号ÿ…...
Mac安装Appium
一、环境依赖 一、JDK环境二、Android-SDK环境（android自动化）三、Homebrew环境四、Nodejs 安装cnpm 五、安装appium六、安装appium-doctor来确认安装环境是否完成七、安装相关依赖 二、重头大戏， 配置wda（WebDriverAgent&#x…...
数据库管理-第153期 Oracle Vector DB AI-05（20240221）
数据库管理153期 2024-02-21 数据库管理-第153期 Oracle Vector DB & AI-05（20240221）1 Oracle Vector的其他特性示例1：示例2 2 简单使用Oracle Vector环境创建包含Vector数据类型的表插入向量数据 总结 数据库管理-第153期 Oracle Vecto…...
通过傅里叶变换进行音频变声变调
文章目录 常见音频变声算法使用Wav库读写音频文件使用pitchShift算法进行音频变调主文件完整代码工程下载地址常见音频变声算法 在游戏或者一些特殊场景下为了提高娱乐性或者保护声音的特征，我们会对音频进行变声变调处理。常用的算法包括: 1.基于傅里叶变换的频域算法，该类…...
Opencv(C++)学习 ARM上引用opencv报相关头文件找不到
简单问题记录，C 与C互相引用时应该多注意类似问题。 问题描述：在项目中，建立了一个interface.h提供了一个C语言兼容的接口void work()，并在对应的interface.cpp中使用OpenCV完成相关处理实现。在PC端测试时，main.cpp成…...
中国服装行业ERP的现状与未来发展
随着全球数字化浪潮的兴起，中国服装行业也在不断探索数字化转型的路径，其中ERP（企业资源计划）系统作为管理和优化企业资源的重要工具，在服装行业中发挥着日益重要的作用。本文将探讨中国服装行业ERP的现状、作用&#…...
Unix与Linux区别
目录 历史和所有权 内核 发行版 开源性质 用户群体 命令行界面 历史和所有权 Unix： Unix是一个操作系统家族的名称，最早由贝尔实验室（Bell Labs）的肖像电机公司（AT&T）开发。最早的Unix版本是在19…...
惠尔顿 网络安全审计系统 任意文件读取漏洞复现
0x01 产品简介 惠尔顿网络安全审计产品致力于满足军工四证、军工保密室建设、国家涉密网络建设的审计要求，规范网络行为，满足国家的规范；支持1-3线路的internet接入、1-3对网桥；含强大的上网行为管理、审计、监控模块；…...
Chrome插件（二）—Hello World！
本小节将指导你从头到尾创建一个基本的Chrome插件，你可以认为是chrome插件开发的“hello world”！ 以下详细描述了各个步骤： 第一步：设置开发环境 确保你拥有以下工具： 文本编辑器：如Visual Studio Cod…...
DBAPI如何使用数组类型参数
DBAPI如何使用数组类型参数 需求 根据多个id去查询学生信息 API创建 在基本信息标签，创建参数ids ，参数类型选择 Array<bigint> 在执行器标签，填写sql，使用in查询 select * from student where id in <foreach ope…...
博途PLC PID仿真(单容水箱液位高度控制含变积分变增益测试)
单容水箱和双荣水箱的微分方程和数值求解，可以参考下面文章链接： https://rxxw-control.blog.csdn.net/article/details/131139432https://rxxw-control.blog.csdn.net/article/details/131139432这篇博客我们利用欧拉求解器在PLC里完成单容水箱的数学建模。PLC也可以和MATL…...
第1集《灵峰宗论导读》
《灵峰宗论》导读。诸位法师，诸位同学，阿弥陀佛！（阿弥陀佛！） 学人很高兴，这次有一个殊胜的因缘来跟大家共同地学习《灵峰宗论》的课程。《灵峰宗论》是蕅益大师一生当中在佛法的修学心得。在蕅…...
nuxt CSS 存放到独立文件进行SEO优化
nuxt CSS 到独立文件 在Nuxt.js中将CSS样式从单个文件分离为多个独立的文件可以通过使用extract-text-webpack-plugin来完成。 首先，确保已经安装了该插件： npm install extract-text-webpack-plugin --save-dev然后，在项目根目录下创建一个…...
台式电脑电源功率越大越费电吗？装机选购多少W电源
要组装一台电脑，我们首先需要选择硬件。 硬件搭配最关键的一点就是CPU和主板的兼容性。 硬件、电源等之间的平衡都需要仔细考虑。 那么台式电脑电源多大功率合适呢？ 下面分享组装电脑电源瓦数选购指南，教您正确选择合适的电源瓦数。 让我们来…...
《TCP/IP详解 卷一》第4章 地址解析协议ARP
目录 4.1 引言 4.2 一个例子 4.3 ARP缓存 4.4 ARP帧格式 4.5 ARP例子 4.6 ARP缓存超时 4.7 代理ARP 4.8 免费ARP和地址冲突检测 4.9 ARP命令 4.10 使用ARP设置嵌入式设备IPv4地址 4.11 与ARP相关攻击 4.12 总结 4.1 引言 地址解析： IPv4：AR…...
如何在pgAdmin中用替换的值更新jsonb列？
我有一个名为files的PostgreSQL表，其中包括一个名为formats的jsonb表。虽然有些行是[null]，但其他行具有此结构的对象： {"thumbnail": {"ext": ".jpg","url": "https://some-url.com/image01.…...