本文涉及知识点
回溯 深度优先搜索
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*4rc) 由于存在大量不存在的路径，所以用时非常少。
每次回溯（深度优先）包括如下工作：
判断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
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业 |
| 。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
