第30559题 单选题
在使用C++实现带钥匙收集的迷宫最短路径问题时，下列关于状态压缩广度优先搜索（状压BFS）的描述正确的是？

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

A

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

B

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

C

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

D

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

程序运行统计
暂无判题统计
知识点：
C++算法-状态压缩广度优先搜索
提交0次 正确率0.00%
答案解析
上一题 下一题