因为在准备谷歌面试中,本来准备最近并不更新刷过的题,多刷些题。但由于这题对我来说意义很大,所以记载了下来。
为了节省些时间,题目题意在这里不复制粘贴了,可以在上面的链接跳转过去。
Solution
Idea
题目是很直接的 BFS , 相比较最简单的迷宫寻路问题,这题增加了钥匙和门,即如果我们想要通过一个门,必须在此之前获得它的钥匙。 注意题目中的数据范围,门和钥匙最多为 10. 故可以用状态压缩记录状态。
Code
1 |
|
闲言
之所以说这题对我意义比较大,是因为在一次很久之前的训练时,有学长出了这道题。
那时候我还是个小白,几乎啥都不会,连 dp 是什么都不知道。那时候做到这个题还是蛮受打击的。讲题目时这题是邓新议(应该是)学长讲的。学长又讲到状压,把拿到我钥匙压缩为一个状态,当时我的心里几乎是崩溃的,因为学长们说的名词我都没有听过, 有一种很无力的感觉。
回去的时候,我一个人走在北操前的路上,有些流泪?因为深深地感受到了自己什么都不知道。于是回去查了 dp,状态压缩一些名词的意思, 这才知道原来 dp 是动态规划的意思。
所以对这题印象蛮深的,过去后一直想再见见这题。昨天刷题时看到题目名字中有个迷宫寻路,心想,不会是有钥匙和门的那道吧。
现在在看这道题,只感觉是一道很基础的题目了,很容易地就能够过掉。对比起来,自己还是学到了些知识的,进步了很多。 也算是给那晚独自一人的自己一个回答吧。