回溯法求解狱中救援最短时间

实验2回溯法是一个计算机科学中的经典算法实践，主要应用于求解路径搜索问题，尤其是在复杂的迷宫或网格环境中。在这个实验中，我们面对的问题是关于一个囚犯A被困在一个N×M大小的矩阵监狱中，其中包含围墙、道路、A本人、A的朋友以及守卫。目标是帮助A的朋友找到他，以便在杀掉守卫后安全通过道路，以找到最短的救援时间。 问题的核心在于实现一种有效的搜索策略，类似于深度优先搜索（DFS）或广度优先搜索（BFS）。然而，由于守卫的存在，每次移动不仅消耗一个时间单位，杀死守卫也需要额外的时间，这使得搜索策略变得更加复杂。在搜索过程中，使用一个变量len来跟踪当前路径的长度，同时维护一个最优解bestlen，初始化为正无穷大，用来记录找到朋友的最短路径长度。 搜索算法的关键步骤如下： 1. 输入与输出格式： - 输入包括监狱矩阵的大小和网格的具体布局，其中 '#' 表示墙，'.' 表示道路，'a' 表示A的位置，'r' 表示A的朋友，'x' 表示守卫。 - 输出是找到朋友所需的最短时间，如果找不到朋友，则输出字符串 "PoorANGELhastostayintheprisonallhislife"。 2. 搜索策略： - 类比于迷宫问题，采用深度优先搜索（DFS）遍历可能的路径。因为A的朋友可能不止一个，所以从A出发，沿着最近的朋友方向前进。 - 在搜索过程中，遇到道路'.'时，路径长度len递增1；遇到守卫'x'时，不仅要走一步，还要额外花费时间杀死守卫，因此len递增2。 - 对每个可能的解空间节点（即朋友位置），更新bestlen，找到更短路径时保留新值。 3. 状态表示与剪枝： - 使用一个二维数组chargrid存储网格状态，visited数组用于标记已访问过的节点，避免重复搜索。 4. 代码实现： - 包含头文件<iostream>和<cstring>，定义常量如最大网格大小(MAXN)和无穷大(INF)，并声明方向偏移量数组dx和dy。 - chargrid和visited数组用于存储网格状态和访问标志，定义一个全局变量bestlen用于存储最优解。 总结来说，这个实验重点在于运用回溯法或者其变体（如带有额外操作的DFS）来解决具有动态代价（杀守卫）的最短路径问题。理解如何维护当前路径长度、最优解和有效地搜索解空间是解决这个问题的关键。