米家龙算法实验报告：18342075 - 脱离地牢的最短路径搜索

本篇实验报告由2018级软件工程专业的学生米家龙撰写，他在中山大学数据科学与计算机学院进行算法设计与分析课程的学习。实验主题是"18342075 米家龙 第四章1：脱离地牢"，其目的是让学生熟悉并掌握广度优先搜索(BFS)和深度优先搜索(DFS)这两种搜索算法在最短路径问题中的应用。 在实验中，题目设定为在一个二维地图上，角色P和H需要寻找脱离地牢的最短路径，地图由WALL（墙）、ROAD（通路）、MELT（熔浆）和字符P/H表示。每一步移动的代价相同，但DFS可能会因为重复路径而浪费操作，且可能因递归层次过深导致内存消耗过大。相比之下，BFS通过循环进行搜索，虽然时间复杂度增加，但能有效减少内存开销。 定义了四个方向移动常量：UP、DOWN、LEFT、RIGHT，以及相应的字符表示。状态的记录采用四维数组res，每个节点由四个整数表示P和H的位置。队列q用于存储待处理的节点，初始化函数init()负责设置初始状态的数组。 在这个实验中，学生需要通过编写程序实现BFS算法，从起点P出发，找到H的最短路径，同时避免无效操作和内存溢出问题。这个过程不仅锻炼了学生的编程技巧，也让他们理解了如何在实际问题中选择合适的搜索策略，以优化时间和空间效率。通过这个实验，学生不仅加深了对算法理论的理解，还提高了实际问题求解的能力。