Back to Leetcode

Readme

BFS/3568.Minimum-Moves-to-Clean-the-Classroom/Readme.md

latest843 B
Original Source

3568.Minimum-Moves-to-Clean-the-Classroom

典型的BFS,但是我们需要定义一个composite state来避免重复。本题中因为最有路径可能需要重复经过相同的cell,所以我们还需要记录每一步时当前的energy,已经访问过的litter。这样所有的状态种类有20*20*50*2^10=2e7,复杂度勉强够用。

具体的做法就是常规的BFS。每次从队列中弹出[x,y,energy,mask],其中mask是一个二进制数,用bit位来记录哪些编号的垃圾已经被清理。从当前[x,y]往四个方向尝试移动,每次移动需要更新energy(减一,或者遇到R就reset),也可能需要更新mask(即遇到L)。在将新状态加入队列之前,查看一下这个state之前是否已经加入过队列(即可以在更早的时间被访问到)以避免重复搜索。