【广度优先搜索】【堆】【C++算法】407. 接雨水 II

class CEnumGridEdge
{
public:
  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);
      }
    }
  }
  const int m_r, m_c;
protected:
  CEnumGridEdge(int r, int c) :m_r(r), m_c(c)
  {
  }
  void Move(int preR, int preC, int r, int c)
  {
    if ((r < 0) || (r >= m_r))
    {
      return;
    }
    if ((c < 0) || (c >= m_c))
    {
      return;
    }
    OnEnumEdge(preR, preC, r, c);
  };
  virtual void OnEnumEdge(int preR, int preC, int r, int c) = 0;
};
class TNeiBoForGrid : public CEnumGridEdge
{
public:
  TNeiBoForGrid(const vector<vector<int>>& grid) :m_grid(grid),
    CEnumGridEdge(grid.size(), grid.front().size())
  {
    m_vNext.assign(m_r, vector < vector<pair<int, int>>>(m_c));
    Init();
  }
  virtual void OnEnumEdge(int preR, int preC, int r, int c)
  { 
    m_vNext[preR][preC].emplace_back(r, c);
  }
  const vector<vector<int>>& m_grid;
  vector < vector < vector<pair<int, int>>>> m_vNext;
};
class Solution {
public:
  int trapRainWater(vector<vector<int>>& heightMap) {
    TNeiBoForGrid neiBo(heightMap);
    vector<vector<int>> vHeight(neiBo.m_r, vector<int>(neiBo.m_c, -1));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> minHeap;
    auto Add = [&](int r, int c, int iHeight)
    {
      if (vHeight[r][c] >= 0)
      {
        return;
      }
      vHeight[r][c] = iHeight;
      minHeap.emplace(iHeight, r, c);
    };
    for (int r = 0; r < neiBo.m_r; r++)
    {
      for (int c = 0; c < neiBo.m_c; c++)
      {
        if ((0 == r) || (neiBo.m_r == r + 1) || (0 == c) || (neiBo.m_c == c + 1))
        {
          Add(r, c, heightMap[r][c]);
        }
      }
    }
    while (minHeap.size())
    {
      auto [height, r, c] = minHeap.top();
      minHeap.pop();
      for (const auto& [nr, nc] : neiBo.m_vNext[r][c])
      {
        Add(nr, nc, max(height, heightMap[nr][nc]));
      }
    }
    int iRet = 0;
    for (int r = 0; r < neiBo.m_r; r++)
    {
      iRet += std::accumulate(vHeight[r].begin(), vHeight[r].end(), 0) - std::accumulate(heightMap[r].begin(), heightMap[r].end(), 0);
    }
    return iRet;
  }
};

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<int>> heightMap;
  {
    Solution sln;
    heightMap = { {1,4,3,1,3,2},{3,2,1,3,2,4},{2,3,3,2,3,1} };
    auto res = sln.trapRainWater(heightMap);
    Assert(4, res);
  }
  
  {
    Solution sln;
    heightMap = { {3,3,3,3,3},{3,2,2,2,3},{3,2,1,2,3},{3,2,2,2,3},{3,3,3,3,3} };
    auto res = sln.trapRainWater(heightMap);
    Assert(10, res);
  }
  
}