我正在做一个项目，我发现自己处于一个 n x n char 符号数组 a、b 或 c 我必须检查第一行和最后一行之间是否有 b 的路径。
示例 YES 输入:
我卡在这一步了？我应该采用一些众所周知的图形搜索算法还是有更好的方法来解决这个问题？我应该添加一个 bool 数组来标记我访问过的单元格吗？
在此先感谢您的时间!
最佳答案
是的，您应该采用图形算法来查找从源到目标的路径。在您的情况下，您有多个来源(第一行中的所有“b”)和多个目标(最后一行中的“b”)。
未加权图上的最短路径可以通过易于实现的 BFS 非常有效地解决.处理多个源的唯一区别是在第一行使用所有 'b' 初始化队列(而不是单个节点)。
在您的图表中，每个“b”单元格都是一个节点，每两个相邻的“b”单元格之间有一条边。
请注意，BFS 是完备的(如果存在，总能找到解决方案)和最优的(找到最短路径)。
关于c++ - 在字符数组中查找路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23217689/