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

作者推荐

本文涉及知识点

深度优先广度优先状态压缩

LeetCode864. 获取所有钥匙的最短路径

给定一个二维网格 grid ，其中：
‘.’ 代表一个空房间
‘#’ 代表一堵墙
‘@’ 是起点
小写字母代表钥匙
大写字母代表锁
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 k 为钥匙/锁的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
示例 1：

在这里插入图片描述

输入：grid = [“@.a…”,“###.#”,“b.A.B”]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。
示例 2：

在这里插入图片描述

输入：grid = [“@…aA”,“…B#.”,“…b”]
输出：6
示例 3:
在这里插入图片描述

输入: grid = [“@Aa”]
输出: -1

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] 只含有 ‘.’, ‘#’, ‘@’, ‘a’-‘f’ 以及 ‘A’-‘F’
钥匙的数目范围是 [1, 6]
每个钥匙都对应一个不同的字母
每个钥匙正好打开一个对应的锁

分析

有多少把钥匙，就有多少趟行程。除第一趟是从起点到某把钥匙外，其它都是钥匙到钥匙。拾取的钥匙不同，会影响到移动次数。最短路径可能被锁阻挡。

{\begin{cases} 6 * 5 * 4 * 3 * 2 * 1 = 720 & D F S 枚 举 拾 取 钥 匙 的 顺 序 \\ 2^{6} * 6 \approx 360 & 枚 举 状 态 ： 那 些 钥 匙 已 经 拾 取 ， 最 后 拾 取 的 钥 匙 \end{cases}

$\begin{cases} 6*5*4*3*2*1=720 & DFS枚举拾取钥匙的顺序 \\ 2^6*6 \approx 360 & 枚举状态：那些钥匙已经拾取，最后拾取的钥匙 \\ \end{cases}$

{6 * 5 * 4 * 3 * 2 * 1 = 720 2^{6} * 6 \approx 360 D FS 枚举拾取钥匙的顺序 枚举状态：那些钥匙已经拾取，最后拾取的钥匙

有些状态是非法状态，不会存在。

代码

核心代码

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);
	}

}

2003年4月

一次BFD，状态：钥匙状态，当前行，当前列。
class Solution {
public:
int shortestPathAllKeys(vector& grid) {
m_r = grid.size();
m_c = grid[0].size();
int iBeginRC = 0;
std::unordered_map mKeyIndex;
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
const char& ch = grid[r][c];
if (‘@’ == ch )
{
iBeginRC = 100 * r + c;
}
if ((ch >= ‘a’) && (ch <= ‘z’))
{
mKeyIndex[ch] = mKeyIndex.size();
}
}
}
m_iKeyMaskNum = 1 << mKeyIndex.size();
std::unordered_map mMaskStep;
std::queue que;
mMaskStep[iBeginRC] = 0;
que.emplace(iBeginRC);
auto Add = [this, &que, &mMaskStep, &grid, &mKeyIndex](const int r, const int c, const int iKeyMask,int iPreSetp)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
const char& ch = grid[r][c];
if (‘#’ == ch)
{//墙直接返回
return;
}
if ((ch >= ‘A’) && (ch <= ‘Z’))
{
int index = mKeyIndex[ch - ‘A’ + ‘a’];
if (!(iKeyMask & (1 << index)))
{//没钥匙开锁
return;
}
}
int iNewKeyMask = iKeyMask;
if ((ch >= ‘a’) && (ch <= ‘z’))
{
int index = mKeyIndex[ch ];
iNewKeyMask |= (1 << index) ;
}
const int iNewMask = iNewKeyMask * 10000 + r * 100 + c;
if (mMaskStep.count(iNewMask))
{
return;
}
mMaskStep[iNewMask] = iPreSetp + 1;
que.emplace(iNewMask);
};
while (que.size())
{
const int iMask = que.front();
const int r = que.front() / 100 % 100;
const int c = que.front() % 100;
const int iKeyMask = que.front() / 10000;
if (iKeyMask + 1 == m_iKeyMaskNum)
{
return mMaskStep[que.front()];
}
que.pop();
Add(r + 1, c, iKeyMask, mMaskStep[iMask]);
Add(r - 1, c, iKeyMask, mMaskStep[iMask]);
Add(r, c + 1, iKeyMask, mMaskStep[iMask]);
Add(r, c - 1, iKeyMask, mMaskStep[iMask]);
}
return -1;
}
int m_r, m_c;
int m_iKeyMaskNum;
};

扩展阅读

视频课程

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

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树首页概览60496 人正在系统学习中

群中有博文配套源码

QQ群名片