Skip to content

Latest commit

 

History

History
 
 

1298.Maximum-Candies-You-Can-Get-from-Boxes

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1298.Maximum-Candies-You-Can-Get-from-Boxes

本题只要读清题意就不难。我们手头有些已经开启的盒子,盒子里面有糖果(收益)、钥匙(可以开启其他盒子)和其他的盒子(可能已经开启,也可能还未开启需要钥匙)。问题是不断打开我们能打开的盒子,最终的总收益是多少。

用BFS可以比较容易解决。队列里永远是还没有被打开的盒子。每一个回合,检查一遍队列里的盒子:1.如果盒子还不能打开(状态是关闭并且没有钥匙),则继续塞回队列。2.如果盒子能够打开,那么就打开它,拿取收益、收藏钥匙、将新盒子塞进队列。

直至队列在经过一个回合之后没有任何变化,即没有任何盒子被打开,那么就说明进入了僵局不会再可能有进展,即终止程序。