第30562题 单选题
在C++中使用状态压缩广度优先搜索（状压BFS）求解带钥匙和门的迷宫最短路径问题时，下列说法正确的是？

已知迷宫规模为n*m（n,m ≤ 50），迷宫中共有k种不同的钥匙（k ≤ 10），走到钥匙格子可拾取对应类型的钥匙，门格子需要持有对应类型的钥匙才能通行，要求求解从起点到终点的最短步数。

A

访问标记数组仅需要设计为二维数组vis[n][m]，记录每个坐标是否被访问过即可

B

由于k≤10，可使用int类型整数的低10位表示当前持有的钥匙集合，每一位对应一类钥匙是否持有，这是状态压缩的核心设计

C

BFS队列中仅需要存储当前所在的坐标(x,y)，不需要存储当前的钥匙持有状态

D

访问标记数组的维度应为vis[k][n][m]，总空间复杂度为O(knm)

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