【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

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]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  vector<vector<int>> grid;
  {
    Solution slu;
    grid = { {3,4,2,1},{4,2,3,1},{2,1,0,0},{2,4,0,0} };
    auto res = slu.minimumVisitedCells(grid);
    Assert(4, res);
  }
  {
    Solution slu;
    grid = { {3,4,2,1},{4,2,1,1},{2,1,1,0},{3,4,1,0} };
    auto res = slu.minimumVisitedCells(grid);
    Assert(3, res);
  }
  {
    Solution slu;
    grid = { {2,1,0},{1,0,0} };
    auto res = slu.minimumVisitedCells(grid);
    Assert(-1, res);
  }
}

class Solution {
public:
  typedef priority_queue<pair<int,int>, vector<pair<int, int>>, greater<>> HTYPE;
  int minimumVisitedCells(vector<vector<int>>& grid) {
    m_r = grid.size();
    m_c = grid.front().size();
    vector<vector<int>> vDis(m_r, vector<int>(m_c, -1));    
    vector< HTYPE> colMinHeaps(m_c);
    for (int r = 0; r < m_r; r++)
    { 
      HTYPE rowMinHeap;
      auto Add = [&](const int r, const int c, int iNewDis)
      {
        vDis[r][c] = iNewDis;
        rowMinHeap.emplace(iNewDis, c + grid[r][c]);
        colMinHeaps[c].emplace(iNewDis, r + grid[r][c]);
      };
      for (int c = 0; c < m_c; c++)
      {
        if (r + c == 0)
        {
          Add(r, c, 1);
          continue;
        }
        while (rowMinHeap.size() && (rowMinHeap.top().second < c))
        {
          rowMinHeap.pop();
        }
        while (colMinHeaps[c].size() && (colMinHeaps[c].top().second < r ))
        {
          colMinHeaps[c].pop();
        }
        int iPreMin = INT_MAX;
        if (rowMinHeap.size())
        {
          iPreMin = min(iPreMin, rowMinHeap.top().first);
        }
        if (colMinHeaps[c].size())
        {
          iPreMin = min(iPreMin, colMinHeaps[c].top().first);
        }
        if (INT_MAX == iPreMin)
        {
          continue;
        }
        Add(r, c, iPreMin + 1);
      }
    }   
    return vDis.back().back();
  }
  int m_r, m_c;
};

class Solution {
public:
  int minimumVisitedCells(vector<vector<int>>& grid) {
    m_r = grid.size();
    m_c = grid.front().size();
    vector<vector<int>> vDis(m_r, vector<int>(m_c, -1));
    vector< vector<pair<int,int>>> cols(m_c);//列（行）号按降序排除，距离按升序排列
    for (int r = m_r-1; r >= 0 ; r-- )
    {
      vector<pair<int, int>> row;
      auto Add = [&](const int r, const int c, int iNewDis)
      {
        vDis[r][c] = iNewDis;
        while (row.size() && (row.back().first >= iNewDis))
        {
          row.pop_back();
        }
        row.emplace_back(iNewDis,c);
        while (cols[c].size() && (cols[c].back().first >= iNewDis))
        {
          cols[c].pop_back();
        }
        cols[c].emplace_back(iNewDis, r);
      };
      auto Cmp = [&](const pair<int, int>& pr, int rc)
      {
        return pr.second > rc;
      };
      for (int c = m_c-1 ; c >= 0 ;c--)
      {
        if (r + c + 2 == m_r+m_c )
        {
          Add(r, c, 1);
          continue;
        }       
        int iPreMin = INT_MAX;
        auto it = std::lower_bound(row.begin(), row.end(), c + grid[r][c], Cmp);
        if (row.end() != it )
        {
          iPreMin = min(iPreMin, it->first);
        }
        auto ij = std::lower_bound(cols[c].begin(), cols[c].end(), r + grid[r][c], Cmp);
        if (cols[c].end() != ij )
        {
          iPreMin = min(iPreMin, ij->first);
        }
        if (INT_MAX == iPreMin)
        {
          continue;
        }
        Add(r, c, iPreMin + 1);
      }
    }
    return vDis.front().front();
  }
  int m_r, m_c;
};