宽度优先搜索。这类题目的关键在于状态的设计。就本题来说,我们需要把当前获得了哪些钥匙也表示进状态里。具体来说,当前状态是一个三元组(x, y, keys),表示小Hi在(x, y)这个位置,获得的钥匙集合是keys。 钥匙最多有5把,所以一共有2^5种可能。再加上100 x 100的位置状态,一共有320000种状态。
需要注意的是一些特殊情况的处理。比如钥匙在上锁的房间里,出口在上锁的房间等。
宽度优先搜索。这类题目的关键在于状态的设计。就本题来说,我们需要把当前获得了哪些钥匙也表示进状态里。具体来说,当前状态是一个三元组(x, y, keys),表示小Hi在(x, y)这个位置,获得的钥匙集合是keys。 钥匙最多有5把,所以一共有2^5种可能。再加上100 x 100的位置状态,一共有320000种状态。
需要注意的是一些特殊情况的处理。比如钥匙在上锁的房间里,出口在上锁的房间等。
直接BFS递归超时了,有什么优化的办法吗?
bfs不需要递归呀