每日leetcode第0085天 1926. Nearest Exit from Entrance in Maze

这是一道快乐的宽度优先搜索题目。

我做宽度优先搜索都很快乐,经常是洋洋洒洒一大堆代码,一次跑通。

 

先是读数据,把maze读进来,把入口读进来。

入门放入可以抵达的reaches队列中。

还有一些需要预处理,比如四周这一圈四条边判断那些是点的就是出口,建一个is_exit二维数组,但是入口不能是出口,这里还要再加一句代码。

判断每个点有没有去过,建一个is_visited二维数组,入口要设置为去过了。

四个方向开一个二维数组direction。

 

然后开始搜索,搜索到队列为空,如果一直搜不到就输出-1。

搜的时候先判断这个点是不是出口了,出口到了就输出返回。

往四个方向走,如果走出地图就不允许,如果去过就不允许,如果是墙就不允许。

把可以去的点叫做nr添加进队列中,然后标记这个点去过了已经。

搜完一个点的四方向,就把这个点弹出。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。