hiho一下第166周《Maze Escape》题目分析

1
0

宽度优先搜索。这类题目的关键在于状态的设计。就本题来说,我们需要把当前获得了哪些钥匙也表示进状态里。具体来说,当前状态是一个三元组(x, y, keys),表示小Hi在(x, y)这个位置,获得的钥匙集合是keys。 钥匙最多有5把,所以一共有2^5种可能。再加上100 x 100的位置状态,一共有320000种状态。

需要注意的是一些特殊情况的处理。比如钥匙在上锁的房间里,出口在上锁的房间等。

1 answer(s)

0

直接BFS递归超时了,有什么优化的办法吗?

write answer 切换为英文 切换为中文


转发分享