【2021.12.28】ctf逆向中的迷宫问题（含exe及wp）

【2021.12.28】ctf逆向中的迷宫问题（含exe及wp）

1、迷宫简介

迷宫问题是ctf逆向中的经典问题。

（1）简单例子

CTF中，一般都是以二维迷宫来考核，二维数组m[x][y]，x代表迷宫的长，y代表迷宫的宽。代表路和墙的字符可以任意（一般为可见字符）代表方向的字符也可以任意（一般为熟悉的wasd）。一般通过for+switch-case语句来判别你输入的路径字符，逐个匹配。

（2）一般的迷宫代码

迷宫数据

走迷宫的判断

2、二维迷宫

（1）实际例题

迷宫地图

关键check函数IDA中的代码

所以，迷宫问题进来首先是要能看懂算法是表示的公告，即确定上下左右对应的字符，然后再根据迷宫判定条件，确定迷宫地图的大小及所有路径，最后即可确定有效路径。

（2）练习

这里有个简单二维迷宫的练习，包含wp

链接：https://pan.baidu.com/s/1Kwi152PZngHknQf20xgcbw
提取码：mq0d

（3）二维迷宫的思考

可以发现，一般遇到的二维迷宫，地图都比较小，直接肉眼就能造出路径，那其实这样的迷宫问题主要就是看我们能否识别迷宫算法。

但当迷宫地图特别大的时候，我们怎么快速寻找路径呢？比如下面这个：

这种，它迷宫地图又大，路径也不唯一，要想凭肉眼走，也不是不可以，只不过太麻烦了。

解决方法：

比较好的方法是利用BFS宽度优先搜索或DFS深度优先搜索，这两个搜索算法。

3、三维迷宫

（1）二维进阶

原始的二维地图为m[x][y]，x代表长，y代表宽

如果我们用多个二维地图堆积起来到h层

（实在找不到好看的图了，这个比较形象。。。。）

即：用三维数组m[x][y][h]来表示地图，这里的h就恰好表示层数。

（2）三维迷宫逆向

难点：获取地图后很难通过自己看地图走出路径

解决：还是利用BFS宽度优先搜索或DFS深度优先搜索，这两个搜索算法。

这里提一下DFS深度优先搜索：

DFS，深度优先搜索，形象点就比如：一个人来到分叉路口时，就是从一个节点一直往深处搜索，直到走到尽头，再往回走，走下一个节点，再次深搜……就相当于来回遍历，一个人走迷宫。

所以，dfs是运用递归的方法，基于回溯的思想。而回溯就是基于栈结构。栈结构的话，直接用数组来实现就可以了。

类似这样：

（3）练习

这里有个简单三维迷宫的练习，包含wp

链接：https://pan.baidu.com/s/1f3Ki3T7lSttTLGkORsRopg
提取码：qcmj

4、总结

二维迷宫比较简单，三维迷宫比较抽象，需要多练习才能熟悉。