在使用C++实现带钥匙收集的迷宫最短路径问题时,下列关于状态压缩广度优先搜索(状压BFS)的描述正确的是?

ga308197 单选题 共 个子题

已知迷宫中最多存在6种不同的钥匙(对应编号0~5),同种钥匙有多把时只需收集一次即可打开所有对应类型的门,只有持有对应类型钥匙才能通过对应门,求起点到终点的最短移动步数。

A

记录访问状态的vis数组只需开2维,分别记录当前坐标的行和列即可,无需额外维度

B

我们可以用一个6位的二进制整数表示当前持有的钥匙集合,第k位为1代表已持有编号为k的钥匙,总共有2^6=64种不同的钥匙状态

C

状压BFS无法保证得到的路径是最短路径,需要改用深度优先搜索遍历所有可能的路径才能得到最优解

D

遇到门时,不管当前持有钥匙状态如何,都可以直接将该位置的状态加入队列

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧