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

本文涉及知识点

回溯 深度优先搜索

LeetCode980. 不同路径 III

在二维网格 grid 上，有 4 种类型的方格：
1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
示例 1：
输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：

  1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,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
    解释：我们有以下四条路径：
  3. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
  4. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
  5. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
  6. (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;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

测试用例

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);
	}
	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

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;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96

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;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览61211 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/137916134"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！