迷宫问题设计实验报告

课程设计题目：迷宫问题设计实验

一、问题描述

有一个 n * m 的迷宫，给定入口和出口，求路径。

二、概要设计

1. 算法的设计

采用BFS（Breadth-first search，广度优先搜索）。

伪代码如下

1. 队列初始化
2. 入口点坐标进队并标记来过
3. 当队列不为空时循环执行下述操作：
    3.1 (x, y) <-- 队头元素出队
    3.2 沿顺时针试探每一个方向，记为(to_x, to_y)，如果可走且没来过：
        3.2.1 标记(to_x, to_y)来过
        3.2.2 记录(to_x, to_y)的前驱为(x, y)
        3.2.3 (to_x, to_y)进队

每个节点至多来一次，故至多进队一次，所以算法复杂度如下

时间复杂度	空间复杂度
$O(nm)$	$O(nm)$

三、详细设计

详见代码。

四、运行与测试

1. 测试环境

运行环境：Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

编译器：g++ (gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project))

编译命令：-g

运行终端：cmd

2. 在调试程序的过程中遇到的问题与解决方案

Windows + VScode + MinGW，当有freopen时debug读入异常，目前无解决方案。

3. 设计的测试数据与测试结果

样例1（可达）

14 16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 
1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 
1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 
1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 
1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 
1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 
1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 
1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 
1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 
1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 
1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 
1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
2 1
10 15

样例2（可达）

30 50
0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1
0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1
0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1
0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0
0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 1
1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0
0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1
1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1
1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0
1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1
1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0
1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 1
0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1
1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1
1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1
0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1
1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0
0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0
1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 0
0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1
1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0
0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1
1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 0
1 1
30 50

样例3（不可达）

14 16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 
1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 
1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 
1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 
1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 
1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 
1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 
1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 
1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 
1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 
1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 
1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
2 1
14 16

4. 程序清单及运行结果

程序清单如下

.\ex4\maze.cpp

样例1（符合预期）（部分运行结果截图）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-soxEePFJ-1618808494317)(ex4/Example1.png)]

样例2（符合预期）（部分运行结果截图）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-20FNqwiJ-1618808494321)(ex4/Example2.png)]

样例3（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week08\ex4>maze
Maze:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1
1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1
1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0
1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1
1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1
1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1
1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1
1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1
1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1
1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Can't reach the exit.

迷宫问题设计实验报告