备案控制台
开发者社区 开发与运维 文章 正文

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

2024-02-27 37
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
云数据库 Redis 版，社区版 2GB
推荐场景：
搭建游戏排行榜
简介： 【广度优先搜索】【网格】【割点】1263. 推箱子

作者推荐

视频算法专题

涉及知识点

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

LeetCode:1263. 推箱子

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏，按规则将箱子 ‘B’ 移动到目标位置 ‘T’ ：

玩家用字符 ‘S’ 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。

地板用字符 ‘.’ 表示，意味着可以自由行走。

墙用字符 ‘#’ 表示，意味着障碍物，不能通行。

箱子仅有一个，用字符 ‘B’ 表示。相应地，网格上有一个目标位置 ‘T’。

玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。

玩家无法越过箱子。

返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

示例 1：

输入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],

[“#”,“T”,“#”,“#”,“#”,“#”],

[“#”,“.”,“.”,“B”,“.”,“#”],

[“#”,“.”,“#”,“#”,“.”,“#”],

[“#”,“.”,“.”,“.”,“S”,“#”],

[“#”,“#”,“#”,“#”,“#”,“#”]]

输出：3

解释：我们只需要返回推箱子的次数。

示例 2：

输入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],

[“#”,“T”,“#”,“#”,“#”,“#”],

[“#”,“.”,“.”,“B”,“.”,“#”],

[“#”,“#”,“#”,“#”,“.”,“#”],

[“#”,“.”,“.”,“.”,“S”,“#”],

[“#”,“#”,“#”,“#”,“#”,“#”]]

输出：-1

示例 3：

输入：grid = [[“#”,“#”,“#”,“#”,“#”,“#”],

[“#”,“T”,“.”,“.”,“#”,“#”],

[“#”,“.”,“#”,“B”,“.”,“#”],

[“#”,“.”,“.”,“.”,“.”,“#”],

[“#”,“.”,“.”,“.”,“S”,“#”],

[“#”,“#”,“#”,“#”,“#”,“#”]]

输出：5

解释：向下、向左、向左、向上再向上。

提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 20

grid 仅包含字符 ‘.’, ‘#’, ‘S’ , ‘T’, 以及 ‘B’。

grid 中 ‘S’, ‘B’ 和 ‘T’ 各只能出现一个。

01广度优先搜索

状态：箱子所在行列，人所在行列

人试图向上下左右移动。以左移为例。

{ 如果人可以左移，人左移，加到队首 箱子不在左边 如果人和箱子都可以左移，人箱子左移，加到队尾 箱子在人左边 \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完成后，才能完成2
  template<class T >
  void Init(vector<T>& vPreToNext)
  {
    m_c = vPreToNext.size();
    vector<int> vInDeg(m_c);
    for (int cur = 0; cur < m_c; cur++)
    {
      for (const auto& next : vPreToNext[cur])
      {
        vInDeg[next]++;
      }
    }
    queue<int> que;
    for (int i = 0; i < m_c; i++)
    {
      if (0 == vInDeg[i])
      {
        que.emplace(i);
        m_vLeaf.emplace_back(i);
        OnDo(-1, i);
      }
    }
    while (que.size())
    {
      const int cur = que.front();
      que.pop();
      for (const auto& next : vPreToNext[cur])
      {
        vInDeg[next]--;
        if (0 == vInDeg[next])
        {
          que.emplace(next);
          OnDo(cur, next);
        }
      }
    };
  }
  virtual void OnDo(int pre, int cur) = 0;
  int m_c;
  vector<int> m_vLeaf;
};
struct CVec
{
  int r;
  int c;
};
struct CPos
{ 
  int r = 0, c = 0;
  int ToMask()const { return s_MaxC * r + c; };
  bool operator==(const CPos& o)const
  {
    return (r == o.r) && (c == o.c);
  }
  CPos operator+(const CVec& v)const
  {
    return { r + v.r, c + v.c };
  }
  CPos operator-(const CVec& v)const
  {
    return{ r - v.r, c - v.c };
  }
  CVec operator-(const CPos& o)const
  {
    return {r - o.r,c- o.c};
  }
  inline static  int s_MaxC = 10'000;
};
class CRange
{
public:
  CRange(int rCount, int cCount, std::function<bool(int, int)> funVilidCur):m_r(rCount),m_c(cCount), m_funVilidCur(funVilidCur)
  {
  }
  bool Vilid(CPos pos)const
  {
    return (pos.r >= 0) && (pos.r < m_r) && (pos.c >= 0) && (pos.c < m_c) && m_funVilidCur(pos.r, pos.c);
  }
  const int m_r, m_c;
protected:
  std::function<bool(int, int)> m_funVilidCur;
};
class  CGridToNeiBo
{
public:
  static vector<vector<int>> ToNeiBo(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
  {
    vector<vector<int>> vNeiBo(rCount * cCount);
    auto Move = [&](int preR, int preC, int r, int c)
    {
      if ((r < 0) || (r >= rCount))
      {
        return;
      }
      if ((c < 0) || (c >= cCount))
      {
        return;
      }
      if (funVilidCur(preR, preC) && funVilidNext(r, c))
      {
        vNeiBo[cCount*preR+preC].emplace_back(r*cCount+ c);
      }
    };
    for (int r = 0; r < rCount; r++)
    {
      for (int c = 0; c < cCount; c++)
      {
        Move(r, c, r + 1, c);
        Move(r, c, r - 1, c);
        Move(r, c, r, c + 1);
        Move(r, c, r, c - 1);
      }
    }
    return vNeiBo;
  }
};
template<class T = int>
class CEnumGrid
{
public: 
  static  void EnumGrid(vector<vector<T>>& grid, std::function<void(int, int, T&)> call)
  {
    for (int r = 0; r < grid.size(); r++)
    {
      for (int c = 0; c < grid.front().size(); c++)
      {
        call(r, c, grid[r][c]);
      }
    }
  }
  static  void EnumPos(vector<vector<T>>& grid, vector<tuple<T, CPos&>> vRes)
  {
    EnumGrid(grid, [&vRes](int curR, int curC, T& curV)
      {
        for (auto& [value, pos] : vRes)
        {
          if (curV == value)
          {
            pos = { curR,curC };
          }
        }
      });
  }
  inline static const CVec s_Move4[4] = { {1,0},{0,1},{-1,0},{0,-1} };//上右下左
  enum {UP=0,RIGHT,DOWN,LEFT};
};
class CEnumGridEdge
{
public:
  CEnumGridEdge(int r, int c, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext) :m_r(r), m_c(c)
  {
    m_funVilidCur = funVilidCur;
    m_funVilidNext = funVilidNext;
    m_vNext.assign(m_r, vector < vector<pair<int, int>>>(m_c));
    Init();
  }
  vector<vector<int>> BFS(vector<pair<int, int>> start, const int endr = -1, const int endc = -1)
  {
    vector<vector<int>> vDis(m_r, vector<int>(m_c, -1));
    queue<pair<int, int>> que;
    for (const auto& [r, c] : start)
    {
      vDis[r][c] = 0;
      que.emplace(make_pair(r, c));
    }
    while (que.size())
    {
      const auto [r, c] = que.front();
      que.pop();
      for (const auto [nr, nc] : m_vNext[r][c])
      {
        if (-1 != vDis[nr][nc])
        {
          continue;
        }
        vDis[nr][nc] = vDis[r][c] + 1;
        if ((endr == nr) && (endc == nc))
        {
          break;
        }
        que.emplace(make_pair(nr, nc));
      }
    }
    return vDis;
  }
  const int m_r, m_c;
  vector < vector < vector<pair<int, int>>>> m_vNext;
protected:
  void Init()
  {
    for (int r = 0; r < m_r; r++)
    {
      for (int c = 0; c < m_c; c++)
      {
        Move(r, c, r + 1, c);
        Move(r, c, r - 1, c);
        Move(r, c, r, c + 1);
        Move(r, c, r, c - 1);
      }
    }
  }
  void Move(int preR, int preC, int r, int c)
  {
    if ((r < 0) || (r >= m_r))
    {
      return;
    }
    if ((c < 0) || (c >= m_c))
    {
      return;
    }
    if (m_funVilidCur(preR, preC) && m_funVilidNext(r, c))
    {
      m_vNext[preR][preC].emplace_back(r, c);
    }
  };
  std::function<bool(int, int)> m_funVilidCur, m_funVilidNext;
};
class CBFS
{
public:
  CBFS(int iStatuCount, int iInit = -1) :m_iStatuCount(iStatuCount), m_iInit(iInit)
  {
    m_res.assign(iStatuCount, iInit);
  }
  bool Peek(int& statu)
  {
    if (m_que.empty())
    {
      return false;
    }
    statu = m_que.front();
    m_que.pop_front();
    return true;
  }
  void PushBack(int statu, int value)
  {
    if (m_iInit != m_res[statu])
    {
      return;
    }
    m_res[statu] = value;
    m_que.push_back(statu);
  }
  void PushFront(int statu, int value)
  {
    if (m_iInit != m_res[statu])
    {
      return;
    }
    m_res[statu] = value;
    m_que.push_front(statu);
  }
  int Get(int statu)
  {
    return m_res[statu];
  }
private:
  const int m_iStatuCount;
  const int m_iInit;
  deque<int> m_que;
  vector<int> m_res;
};
class CBFS2 : protected CBFS
{
public:
  CBFS2(int iStatuCount1, int iStatuCount2, int iInit = -1) :CBFS(iStatuCount1* iStatuCount2, iInit), m_iStatuCount2(iStatuCount2)
  {
  }
  bool Peek(int& statu1, int& statu2)
  {
    int statu;
    if (!CBFS::Peek(statu))
    {
      return false;
    }
    statu1 = statu / m_iStatuCount2;
    statu2 = statu % m_iStatuCount2;
    return true;
  }
  void PushBack(int statu1, int statu2, int value)
  {
    CBFS::PushBack(statu1 * m_iStatuCount2 + statu2, value);
  }
  void PushFront(int statu1, int statu2, int value)
  {
    CBFS::PushFront(statu1 * m_iStatuCount2 + statu2, value);
  }
  int Get(int statu1, int statu2)
  {
    return CBFS::Get(statu1 * m_iStatuCount2 + statu2);
  }
private:
  const int m_iStatuCount2;
};
class CBFS3 : protected CBFS2
{
public:
  CBFS3(int iStatuCount1, int iStatuCount2, int iStatuCount3, int iInit = -1) :CBFS2(iStatuCount1, iStatuCount2* iStatuCount3, iInit), m_iStatuCount3(iStatuCount3)
  {
  }
  bool Peek(int& statu1, int& statu2, int& statu3)
  {
    int statu23;
    if (!CBFS2::Peek(statu1, statu23))
    {
      return false;
    }
    statu2 = statu23 / m_iStatuCount3;
    statu3 = statu23 % m_iStatuCount3;
    return true;
  }
  void PushBack(int statu1, int statu2, int statu3, int value)
  {
    CBFS2::PushBack(statu1, statu2 * m_iStatuCount3 + statu3, value);
  }
  void PushFront(int statu1, int statu2, int statu3, int value)
  {
    CBFS2::PushFront(statu1, statu2 * m_iStatuCount3 + statu3, value);
  }
  int Get(int statu1, int statu2, int statu3)
  {
    return CBFS2::Get(statu1, statu2 * m_iStatuCount3 + statu3);
  }
  const int m_iStatuCount3;
};
class CBFS4 : protected CBFS3
{
public:
  CBFS4(int iStatuCount1, int iStatuCount2, int iStatuCount3, int iStatuCount4, int iInit = -1) :CBFS3(iStatuCount1, iStatuCount2, iStatuCount3* iStatuCount4, iInit), m_iStatuCount4(iStatuCount4)
  {
  }
  bool Peek(int& statu1, int& statu2, int& statu3, int& statu4)
  {
    int statu34;
    if (!CBFS3::Peek(statu1, statu2, statu34))
    {
      return false;
    }
    statu3 = statu34 / m_iStatuCount4;
    statu4 = statu34 % m_iStatuCount4;
    return true;
  }
  void PushBack(int statu1, int statu2, int statu3, int statu4, int value)
  {
    CBFS3::PushBack(statu1, statu2, statu3 * m_iStatuCount4 + statu4, value);
  }
  void PushFront(int statu1, int statu2, int statu3, int statu4, int value)
  {
    CBFS3::PushFront(statu1, statu2, statu3 * m_iStatuCount4 + statu4, value);
  }
  int Get(int statu1, int statu2, int statu3, int statu4)
  {
    return CBFS3::Get(statu1, statu2, statu3 * m_iStatuCount4 + statu4);
  }
  const int m_iStatuCount4;
};
class CCutPointEx
{
public:
  CCutPointEx(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
  {
    m_vTime.assign(m_iSize, -1);  
    m_vCutRegion.resize(m_iSize);
    m_vNodeToRegion.assign(m_iSize,-1);
    m_vCut.assign(m_iSize, false);
    for (int i = 0; i < m_iSize; i++)
    {
      if (-1 != m_vTime[i])
      {
        continue;
      }
      dfs(i, -1, vNeiB);
      m_iRegionCount++;
    }
  }
  bool Visit(int src, int dest, int iCut)
  {
    if (m_vNodeToRegion[src] != m_vNodeToRegion[dest])
    {
      return false;//不在一个连通区域
    }
    if (!m_vCut[iCut])
    {
      return true;
    }
    const int r1 = GetCutRegion(iCut,src);
    const int r2 = GetCutRegion(iCut, dest);
    return r1 == r2;
  }
protected:
  int dfs(int cur, int parent, const vector<vector<int>>& vNeiB)
  {   
    auto& curTime = m_vTime[cur];     
    m_vNodeToRegion[cur] = m_iRegionCount;
    curTime = m_iTime++;    
    int iCutChild=0;
    int iMinTime = curTime;
    for (const auto& next : vNeiB[cur])
    {
      if (next == parent)
      {
        continue;
      }
      if (-1 != m_vTime[next])
      {
        iMinTime = min(iMinTime, m_vTime[next]);
        continue;
      }     
      int iChildBeginTime = m_iTime;
      const int iChildMinTime = dfs(next, cur, vNeiB);
      iMinTime = min(iMinTime, iChildMinTime);
      if (iChildMinTime >= curTime)
      {
        iCutChild++;
        m_vCutRegion[cur].push_back({ iChildBeginTime,m_iTime });
      };
    }
    m_vCut[cur] = (iCutChild + (-1 != parent)) >= 2;
    return iMinTime;
  } 
  int GetCutRegion(int iCut, int iNode)const 
  {
    const auto& v = m_vCutRegion[iCut];
    auto it = std::upper_bound(v.begin(), v.end(), m_vTime[iNode],[](int time, const std::pair<int, int>& pr) {return time < pr.first; });
    if (v.begin() == it)
    {
      return v.size();
    }
    --it;
    return (it->second > m_vTime[iNode]) ? (it - v.begin()) : v.size();
  }
  int m_iTime = 0;  
  const int m_iSize;
  int m_iRegionCount=0;
  vector<int> m_vTime;//各节点到达时间，从0开始。 -1表示未处理
  vector<bool> m_vCut;
  vector<int> m_vNodeToRegion;
  vector<vector<pair<int,int>>> m_vCutRegion;
};
class Solution {
public:
  int minPushBox(vector<vector<char>>& grid) {    
    auto Vilid = [&](int r, int c) {return '#' != grid[r][c]; };
    CRange range(grid.size(), grid.front().size(), Vilid);  
    CPos::s_MaxC = range.m_c;   
    auto neiBo = CGridToNeiBo::ToNeiBo(range.m_r, range.m_c, Vilid, Vilid);   
    CCutPointEx cutPoint(neiBo);
    auto Visit = [&](CPos s, CPos d, CPos b){     
      return range.Vilid(d) && cutPoint.Visit(s.ToMask(),d.ToMask(),b.ToMask());
    };
    CBFS3 bfs(range.m_r, range.m_c, 4);
    CPos sInit,tInit,bInit;
    CEnumGrid<char>::EnumPos(grid, { { 'B',bInit },{'T',tInit},{'S',sInit} });
    auto MovePeo = [&](CPos peo, CPos bCur, int iCurDis)    {
      for (int i = 0; i < 4; i++) {
        if (Visit(peo, bCur + CEnumGrid<>::s_Move4[i], bCur)) {
          bfs.PushFront(bCur.r, bCur.c, i, iCurDis);
        }
      }
    };
    MovePeo(sInit, bInit, 0);
    int br1, bc1, pd;
    while (bfs.Peek(br1, bc1, pd))    {
      CPos bCur = { br1,bc1 };
      CPos peo = bCur + CEnumGrid<>::s_Move4[pd];
      const int CurDis = bfs.Get(br1, bc1, pd);
      if (bCur == tInit )     {
        return CurDis;  } 
      MovePeo(peo, bCur, CurDis);
      auto dest = bCur - CEnumGrid<>::s_Move4[pd];
      if (range.Vilid(dest)){
        bfs.PushBack(dest.r, dest.c, pd, CurDis + 1);
      }
    }     
    return -1;
  }
};

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;

};


文章标签：
云数据库 ClickHouse
云数据库 Redis 版
Java
C++
测试技术
定位技术
算法
闻缺陷则喜何志丹
目录
相关文章
微芒不朽
|
5天前
|
算法 前端开发
前端算法-岛屿的最大面积-DFS(深度优先搜索)
前端算法-岛屿的最大面积-DFS(深度优先搜索)
微芒不朽
11 0
微芒不朽
|
5天前
|
算法 前端开发
前端算法 岛屿的最大面积 DFS(深度优先搜索)
前端算法 岛屿的最大面积 DFS(深度优先搜索)
微芒不朽
11 0
微芒不朽
|
5天前
|
JavaScript
【leetcode】221. 最大正方形 动态规划法
【leetcode】221. 最大正方形 动态规划法
微芒不朽
12 0
闻缺陷则喜何志丹
|
5天前
|
测试技术
【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率
【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率
闻缺陷则喜何志丹
32 2
闻缺陷则喜何志丹
|
5天前
|
算法 测试技术 C#
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
闻缺陷则喜何志丹
43 0
存在morning
|
5天前
|
存储 算法 程序员
【算法训练-搜索算法 一】【DFS网格搜索框架】岛屿数量、岛屿的最大面积、岛屿的周长
【算法训练-搜索算法 一】【DFS网格搜索框架】岛屿数量、岛屿的最大面积、岛屿的周长
存在morning
78 0
夏微凉
|
11月前
洛谷P1162 填涂颜色——广搜
洛谷P1162 填涂颜色——广搜
夏微凉
55 0
LightOf
洛谷P3194 [HNOI2008]水平可见直线（计算几何+单调栈）
洛谷P3194 [HNOI2008]水平可见直线（计算几何+单调栈）
LightOf
77 0
洛谷P3194 [HNOI2008]水平可见直线（计算几何+单调栈）
zzqwtc
|
算法 定位技术 Perl
单源最短路的建图方式
笔记
zzqwtc
73 0
单源最短路的建图方式
流楚丶格念
7-1 迷宫寻路 (20分)
7-1 迷宫寻路 (20分)
流楚丶格念
198 0