C++ 中矩阵中最短的获得食物的路径

在本文中，我们将讨论如何在 C++ 中找到矩阵中获取食物的最短路径。在这里，考虑一个矩阵数组[][]，其左上角由一个星号 (*) 表示，表示我们当前的位置，包含食物的单元格用井号 (#) 表示，'O' 表示自由空间，'X' 表示障碍物。在描述食物单元格位置的矩阵网格中，您的目标是找到从您的位置到任何食物单元格的最短路径，并返回最短路径的步数，如果不存在路径，则返回 -1。

建议的解决方案将实现一个基于多个来源的 BFS（广度优先搜索）算法。在此算法中，BFS 从指定节点开始，并首先检查当前级别上的相邻节点，然后再进入下一个级别。此示例中 BFS 的关键方面是其内在属性，该属性确保完全探索指定距离处的每个单元格，然后继续探索更高距离处的单元格。

分步方法

• 首先，提供一个源 (q) 来存储访问的单元格。
• 将网格值 ('*', '#', 'O') 映射到整数 (1, 2, 3) 在使用它们时会很有帮助。
• 将起始点 '*' 在行中输入队列。
• 接下来，使用队列实现广度优先搜索 (BFS) 以遍历网格。
• 对于从队列中弹出的每个单元格
• 如果它是食物单元格 ('#')，则更改其最短路径长度，然后退出 BFS 循环。
• 如果它是空空间 ("O")，则标记它并继续探索相邻单元格。
• 以尽可能短的时间探索食物单元格的方式应用优先级队列。
• 在最后阶段，BFS 返回到任何食物单元格的最短路径的长度。如果存在一个，则返回 -1。

示例

让我们看一个如何在 C++ 中找到矩阵中获取食物的最短路径的示例。

输出

2

说明

• 此示例使用 2D 向量 gridmatrix 作为输入并返回最短路径长度。Que 变量是一个队列，其中存储了有关网格中单元格的信息。队列中的每个元素都是一个包含四个值的向量：类型、距离、行和列。这些值是单元格的类型、距起始单元格的距离以及单元格的坐标。
• directionGrid 是一个 2D 向量，表示网格的四个主要方向（上、下、左、右）。
• 它首先捕获矩阵中的行数和列数。然后，它遍历整个矩阵，以找到起始单元格，即点符号 ('.')。起始单元格的位置将通过放置一个名为“Que”的队列来确定，该队列包含其坐标、类型和行列表格值，如 [1,0, 行, 列]。
• 程序的主要部分是一个 BFS 循环，它一直持续到 Que 队列 为空。在每一步中，它从 Que 中随机取出一个单元格并测试它是否是食物单元格（类型 2）。如果不是，它会更新最短路径长度并跳出循环。
• 代码读取所有相邻单元格的右、左、上、下位置。然后，如果一个单元格满足以下所有四个条件：是开放单元格 ('O') 或食物单元格 ('#')，位于网格边界内且尚未访问，则将其标记为已访问并以适当的类型和距离值入队到 'Que' 中。
• 最后，代码输出最小路径长度，该长度表示到达食物单元格所需的步数。否则，值为 -1。