【深度优化】【广度优先】【状态压缩】864. 获取所有钥匙的最短路径

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;
};
template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
  *seft = min(*seft,(ELE) other);
}
class Solution{
public:
  int shortestPathAllKeys(vector<string>& grid) {
    m_r = grid.size();
    m_c = grid.front().size();
    std::pair<int, int> start;
    vector< pair<int, int>> vKeys(6, { -1,-1 });
    for (int r = 0; r < m_r; r++)
    {
      for (int c = 0; c < m_c; c++)
      {
        const char& ch = grid[r][c];
        if ('@' == ch)
        {
          start = { r,c };
        }
        else if ((ch >= 'a') && (ch <= 'f'))
        {
          vKeys[ch-'a'] = { r,c };
          m_iKeyMask |= (1 << (ch - 'a'));
        }
      }
    }
    vector<vector<int>> vDis(1 << 6, vector<int>(6, INT_MAX));
    vDis[0][0] = 0;
    for (int hasKey = 0; hasKey < (1 << 6); hasKey++)
    {
      for (int endKey = 0; endKey < 6; endKey++)
      {
        auto VILID = [&hasKey, &grid](int r, int c)
        {
          const auto& ch = grid[r][c];
          if ('#' == ch)
          {
            return false;
          }
          if ((ch >= 'A') && (ch <= 'F'))
          {
            return bool(hasKey & (1 << (ch - 'A')));
          }
          return true;
        };
        if (INT_MAX == vDis[hasKey][endKey])
        {
          continue;
        }
        auto startCur = (0 == hasKey) ? start : vKeys[endKey];
        int needKey = m_iKeyMask ^ hasKey;
        CEnumGridEdge enumGrid(grid.size(), grid[0].size(), VILID, VILID);
        auto vCurDis = enumGrid.BFS({ startCur });
        for (int i = 0; i < vKeys.size(); i++)
        {
          if ((1 << i) & needKey)
          {
            const int iNewHasKey = hasKey | (1 << i);       
            if (-1 == vCurDis[vKeys[i].first][vKeys[i].second])
            {//无法到达第i个钥匙
              continue;
            }
            MinSelf(&vDis[iNewHasKey][i] , vDis[hasKey][endKey] + vCurDis[vKeys[i].first][vKeys[i].second]);
          }
        }
      }
    }
    const int iMin = *std::min_element(vDis[m_iKeyMask].begin(), vDis[m_iKeyMask].end());
    return (INT_MAX==iMin)? -1 : iMin;
  }
  int m_r, m_c;
  int m_iKeyMask=0;
};

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<string> grid;
  {
    Solution sln;
    grid = { "@aA" };
    auto res = sln.shortestPathAllKeys(grid);
    Assert(1, res);
  }
  {
    Solution sln;
    grid = { "@.a..", "###.#", "b.A.B" };
    auto res = sln.shortestPathAllKeys(grid);
    Assert(8, res);
  }
  
  {
    Solution sln;
    grid = { "@..aA","..B#.","....b" };
    auto res = sln.shortestPathAllKeys(grid);
    Assert(6, res);
  }
  {
    Solution sln;
    grid = { "@Aa" };
    auto res = sln.shortestPathAllKeys(grid);
    Assert(-1, res);
  }
}