【回溯深度优先搜索】980. 不同路径 III-阿里云开发者社区

【回溯深度优先搜索】980. 不同路径 III

2024-05-07 14

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【回溯深度优先搜索】980. 不同路径 III

本文涉及知识点

回溯深度优先搜索

LeetCode980. 不同路径 III

在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。

2 表示结束方格，且只有一个结束方格。

0 表示我们可以走过的空方格。

-1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

示例 1：

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

输出：2

解释：我们有以下两条路径：

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
示例 2：
输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：4
解释：我们有以下四条路径：
(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
(0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
示例 3：
输入：[[0,1],[2,0]]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。
提示：
1 <= grid.length * grid[0].length <= 20

回溯

m_iNeed 记录起始格和可以通过的格子数量。

m_visit 记录那些单元格已经访问。

两轮循环：第一轮计算m_iNeed 。第二轮寻找起始格。

时间复杂度： O(rc*4^rc) 由于存在大量不存在的路径，所以用时非常少。

每次回溯（深度优先）包括如下工作：

判断r,c是否合法。

r,c是否能通过。

如果是终点格，判断是否通过所有单格。并返回。

如果当前路径已经访问当前格，返回。

为当前格子设置已访问标记。

has++

DFS当前格的相邻格

has–

取消当前格已访问标记

代码

核心代码

class Solution {
public:
  int uniquePathsIII(vector<vector<int>>& grid) {
    m_visit.assign(grid.size(), vector<bool>(grid[0].size()));
    for (int r = 0; r < grid.size(); r++) {
      for (int c = 0; c < grid[0].size(); c++) {
        if (0 == grid[r][c]) {
          m_iNeed++;
        }
      }
    }
    for (int r = 0; r < grid.size(); r++) {
      for (int c = 0; c < grid[0].size(); c++) {
        if (1 == grid[r][c]) {
          DFS(grid, r, c, 0);
        }
      }
    }
    return m_iRet;
  }
  void DFS(const vector<vector<int>>& grid, int r, int c,int iHas) {
    if ((r < 0) || (r >= grid.size())) { return; }
    if ((c < 0) || (c >= grid[0].size())) { return; }
    if (-1 == grid[r][c]) { return; }
    if (2 == grid[r][c]) {
      if (m_iNeed == iHas) {
        m_iRet++;
      }
      return;
    }
    if (m_visit[r][c]) { return; }
    m_visit[r][c] = true;
    iHas++;
    for (int i = 0; i < sizeof(m_move) / sizeof(m_move[0]); i++) {
      DFS(grid, r + m_move[i][0], c + m_move[i][1],iHas);
    }
    iHas--;
    m_visit[r][c] = false;
  }
  vector<vector<bool>> m_visit;
  int m_iRet = 0;
  int m_move[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
  int m_iNeed = 1;
};

测试用例

template<class T>
void Assert(const T& t1, const T& 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>> grid;
  {
    Solution sln;
    grid = { {0,1},{2,0} };
    auto res = sln.uniquePathsIII(grid);
    Assert(0, res);
  }
  {
    Solution sln;
    grid = { {1,0,0,0},{0,0,0,0},{0,0,2,-1} };
    auto res = sln.uniquePathsIII(grid);
    Assert(2, res);
  }
  {
    Solution sln;
    grid = { {1,0,0,0},{0,0,0,0},{0,0,0,2} };
    auto res = sln.uniquePathsIII(grid);
    Assert(4, res);
  }
  
}

2023年7月

class Solution {
public:
  int uniquePathsIII(vector<vector<int>>& grid) {
    m_r = grid.size();
    m_c = grid[0].size();
    
    int indexBegin;
    int index = 0;
    for (int r = 0; r < m_r; r++)
    {
      for (int c = 0; c < m_c; c++)
      {
        if (-1 == grid[r][c])
        {         
          continue;
        }
        if (1 == grid[r][c])
        {
          indexBegin = index;
        }
        else if (2 == grid[r][c])
        {
          m_indexEnd = index;
        }
        else
        {
          m_i02Num++;
        }
        grid[r][c] = index++;
      }
    }
    m_vNeiBo.resize(index);
    for (int r = 0; r < m_r; r++)
    {
      for (int c = 0; c < m_c; c++)
      {
        if (-1 == grid[r][c])
        {
          continue;
        }
        Add(m_vNeiBo[grid[r][c]], r + 1, c, grid);
        Add(m_vNeiBo[grid[r][c]], r - 1, c, grid);
        Add(m_vNeiBo[grid[r][c]], r , c + 1, grid);
        Add(m_vNeiBo[grid[r][c]], r , c - 1, grid);
      }
    }
    bool aHas[20] = { false };
    dfs(indexBegin, -1, 0, aHas);
    return m_iRet;
  }
  void dfs(int cur, int parent, int iNodeNum, bool* aHas)
  {
    if (aHas[cur])
    {
      return;//已经访问
    }
    if (cur == m_indexEnd)
    {
      if (m_i02Num == iNodeNum)
      {
        m_iRet++;
      }
      return;
    }
    aHas[cur] = true;
    for (const auto& next : m_vNeiBo[cur])
    {
      if (next == parent)
      {
        continue;
      } 
      dfs(next, cur, iNodeNum + 1, aHas);     
    }
    aHas[cur] = false;
  }
  void Add(vector<int>& vNeiBo, int r, int c,const vector<vector<int>>& grid)
  {
    if ((r < 0) || (r >= m_r))
    {
      return;
    }
    if ((c < 0) || (c >= m_c))
    {
      return;
    }
    if (-1 != grid[r][c])
    {
      vNeiBo.emplace_back(grid[r][c]);
    }
  }
  int m_r,m_c;
  int m_indexEnd;
  vector<vector<int>> m_vNeiBo;
  int m_i02Num = 1;
  int m_iRet = 0;
};

2023年4月

class Solution {
public:
  int uniquePathsIII(vector<vector<int>>& grid) {
    m_r = grid.size();
    m_c = grid[0].size();
    int iNeedVisit = 0;
    int iStartR = 0,iStartC=0, iEndMask = 0;
    for (int r = 0; r < m_r; r++)
    {
      for (int c = 0; c < m_c; c++)
      {
        const int iRowColMask = m_c*r + c;
        if (-1 != grid[r][c])
        {
          iNeedVisit |= (1 << iRowColMask);
        }
        if (1 == grid[r][c])
        {
          iStartR = r;
          iStartC = c;
        }
        else if (2 == grid[r][c])
        {
          iEndMask = iRowColMask;
        }
      }
    }
    std::queue<int> que;
    std::unordered_set<int> setHasDo;
    auto Add = [&](const int r, const int c, int iVisite)
    {
      if ((r < 0) || (r >= m_r))
      {
        return;
      }
      if ((c < 0) || (c >= m_c))
      {
        return;
      }
      if (-1 == grid[r][c])
      {
        return;
      }
      const int iRowColMask = m_c*r + c;
      if (iVisite &(1 << iRowColMask))
      {
        return;//已经访问
      }
      const int iMask = (iVisite | (1 << iRowColMask)) * 100 + iRowColMask;
      if (setHasDo.count(iMask))
      {
      //  return;
      }
      setHasDo.emplace(iMask);
      que.emplace(iMask);
    };
    Add(iStartR, iStartC, 0);
    int iRet = 0;
    while (que.size())
    {
      const int iRowColMask = que.front() % 100;
      const int iVisite = que.front() / 100;
      que.pop();
      if ((iRowColMask == iEndMask) && (iVisite == iNeedVisit))
      {
        iRet++;
        continue;
      }
      const int r = iRowColMask / m_c;
      const int c = iRowColMask % m_c;
      Add(r + 1, c, iVisite);
      Add(r - 1, c, iVisite);
      Add(r, c + 1, iVisite);
      Add(r, c - 1, iVisite);
    }
    return iRet;
  }
  int m_r, m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业
。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

【回溯深度优先搜索】980. 不同路径 III

本文涉及知识点

LeetCode980. 不同路径 III

回溯

代码

核心代码

测试用例

2023年7月

2023年4月

扩展阅读

视频课程

相关下载

测试环境

热门文章

最新文章

相关电子书

【回溯 深度优先搜索】980. 不同路径 III

本文涉及知识点

LeetCode980. 不同路径 III

回溯

代码

核心代码

测试用例

2023年7月

2023年4月

扩展阅读

视频课程

相关下载

测试环境

热门文章

最新文章

相关电子书

【回溯深度优先搜索】980. 不同路径 III