re-迷宫题学习

re中的迷宫问题有以下特点:

在内存中布置一张 "地图"
将用户输入限制在少数几个字符范围内.
一般只有一个迷宫入口和一个迷宫出口

布置的地图可以由可显字符 (比如#和*)组合而成 (这非常明显, 查看字符串基本就知道这是个迷宫题了.), 也可以单纯用不可显的十六进制值进行表示. 可以将地图直接组成一条非常长的字符串, 或是一行一行分开布置. 如果是一行一行分开布置的话, 因为迷宫一般都会比较大, 所以用于按行(注意, 布置并非按顺序布置, 每行都对应一个具体的行号, 你需要确定行号才能还原迷宫地图) 布置迷宫的函数会明显重复多次.

而被限制的字符通常会是一些方便记忆的组合 (不是也没办法), 比如w/s/a/d, h/j/k/l, l/r/u/d这样的类似组合. 当然各个键具体的操作需要经过分析判断 (像那种只用一条字符串表示迷宫的, 就可以用t键表示向右移动12个字符这样). 对于二维的地图, 一般作者都会设置一个X坐标和一个Y坐标用于保存当前位置. 我们也可以根据这个特点来入手分析.

一般情况下, 迷宫是只有 1 个入口和 1 个出口, 像入口在最左上角(0, 0)位置, 而出口在最右下角(max_X, max_Y)处. 但也有可能是出口在迷宫的正中心, 用一个Y字符表示等等. 解答迷宫题的条件也是需要根据具体情况判断的.

当然迷宫的走法可能不止 1 条, 也有情况是有多条走法, 但是要求某一个走法比如说代价最小. 那么这就可以变相为一个算法问题.

DFS和BFS算法讲解

深度优先遍历（Depth Fist Search）

什么是深度优先，用树来看就是从一个结点开始，沿着其中一条支路，一直搜索下去直到尽头；然后再原路返回起点，再找另一条路不断遍历下去。
用迷宫来讲的话，就是从起点开始，不断向四周的格子走，不考虑回头的话，总有到尽头的时候（终点或是一堵墙）。到尽头后，回到起点，再沿着没有走过的路走一次，不断重复这个过程。

深度优先算法有俩种实现方法，一种是利用递归实现，一种是非递归实现。

广度优先遍历（Breath First Search）

广度优先遍历指的是从图的一个未遍历的结点出发，先遍历这个点的相邻结点，再依次遍历每个相邻节点的相邻节点。
在迷宫的例子里，就是说我们按照走1步能到达的位置，走2步能到达的位置…这样的顺序逐一搜索，直到不再有能到达的位置。

深度优先利用的是栈实现，广度优先利用的是队列实现。

具体代码实现部分可以看[算法]搜索初步: 从迷宫最短路问题来理解DFS和BFS · Issue #14 · Locietta/blogs · GitHub
图文解析可以看图文详解 DFS 和 BFS

步骤和代码实现

maze

NSSCTF的 [SWPUCTF 2021 新生赛]老鼠走迷宫为例子，用深度优先遍历DFS。

maze = [[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1],[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1],[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],[1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1],[1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1],[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],[1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1],[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],[1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1],[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],[1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1],[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],[1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],[1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1]]

这里有一个地方进行了修改，最后一行的倒数第二个位置原本是0，我手动修改成了2；原题有明确该坐标是出口。maze[0][1]处是入口。

具体操作

先写从当前位置前往下一个位置的限制条件；（例如，通行的要求，是否遇到墙；走到终点了）

# 添加限制条件
def check(map, x, y):if (x >= 0) and (x <= 24) and (y >= 0) and (y <= 24):    # 这一行检查(x,y)是否在有效范围内；return (map[x][y] != 1) and ((map[x][y] == 0) or (map[x][y] == 2)) 	# 这里是如果坐标在地图范围内，就检测该坐标是不是障碍物；是不是可以前进的道路或者终点；else:return False

写出当前位置四周的情况，并存入一个列表里。该列表中的每一项包含三个信息（x坐标，y坐标，前进方向）

def gen_nex(map, x, y):all_dir = []if check(map, x - 1, y):all_dir.append((x - 1, y, 'w'))if check(map, x + 1, y):all_dir.append((x + 1, y, 's'))if check(map, x, y - 1):all_dir.append((x, y - 1, 'a'))if check(map, x, y + 1):all_dir.append((x, y + 1, 'd'))return all_dir# all_dir是一个列表，用于存储下一个可能的坐标和前进方向的信息。每个元素都是一个包含三个值的元组，格式如下：(x, y, direction)

写出DFS用递归查找路线

①第一步先写判断dfs成功的条件
②将访问过的值设置成其它特殊值，即我们走过一遍的地方不能再走，不然会出bug，俩个点来回横跳。
③进行递归dfs调用

def check_success(map, x, y):if map[x][y] == 2:return Trueelse:return Falsedef dfs(maze, x, y, path):map = maze.copy()    # 这里用将maze复制给map，避免修改掉原地图。if map[x][y] != 2:map[x][y] = 1if check_success(map, x, y):print(path)return Truenext_point = gen_nex(map, x, y)for n in next_point:pathn = path + n[2]       # 将all_dir列表中的元组的第三个值，即方向传给pathndfs(map, n[0], n[1], pathn)        # 这里开始递归 用all_dir的元组第一二个值和pathn作为参数，进行当前位置的又一次深度优先遍历。

最后再加个尾巴

output = ""
dfs(maze, 0, 1, output)

直接运行

实战分析

[SWPUCTF 2021 新生赛]老鼠走迷宫

这一题是pyinstaller类的题目，前面是简单的python逆向，这里不再进行分析，直接默认分析迷宫步骤开始

在maze下面添加一个for循环，输出maze，会报错，把最下面的return none直接删了，这不是重点不要紧
修改之后的代码，可以直接输出maze

#!/usr/bin/env python
# visit https://tool.lu/pyc/ for more information
# Version: Python 3.7import random
import msvcrt
(row, col) = (12, 12)
(i, j) = (0, 0)
maze = [[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1],[1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1],[1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1],[1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1],[1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1],[1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1],[1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1],[1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1],[1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1],[1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1],[1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1],[1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1],[1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1],[1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1],[1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1],[1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1],[1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1],[1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1],[1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1],[1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1],[1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1],[1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1],[1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1]]
for row in maze:print(row)
print('Mice walk in a maze: wasd to move,q to quit')
print("flag is the shortest path's md5,example:if the shortest path is wasdsdw,the flag is md5('wasdsdw')")
(i, j) = (0, 1)
n = 0
while i == row * 2 and j == col * 2 - 1:print('ohhhh!!!!you did it')breakprint('your position:({},{})'.format(i, j))inp = msvcrt.getch()n += 1ti = itj = jif b'a' == inp and i > 0:tj -= 1elif b'w' == inp and j > 0:ti -= 1elif b's' == inp and j < row * 2:ti += 1elif b'd' == inp and i < col * 2:tj += 1elif b'q' == inp:exit('bye!!')else:print('What???')if maze[ti][tj] == 1:print(random.choice(['no wayy!!',"it's wall",'nop']))continueelif maze[ti][tj] == 0:print(random.choice(['nice!!','yeah!!','Go on']))i = tij = tj

接下来用上面的的DFS,这里不再重复

dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 当前位置四个方向的偏移量
path = []  # 存找到的路径def mark(maze, pos):  # 给迷宫maze的位置pos标"2"表示“倒过了”maze[pos[0]][pos[1]] = 2def passable(maze, pos):  # 检查迷宫maze的位置pos是否可通行return maze[pos[0]][pos[1]] == 0def find_path(maze, pos, end):mark(maze, pos)if pos == end:print(pos, end=" ")  # 已到达出口，输出这个位置。成功结束path.append(pos)return Truefor i in range(4):  # 否则按四个方向顺序检查nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]# 考虑下一个可能方向if passable(maze, nextp):  # 不可行的相邻位置不管if find_path(maze, nextp, end):  # 如果从nextp可达出口，输出这个位置，成功结束print(pos, end=" ")path.append(pos)return Truereturn Falsedef see_path(maze, path):  # 使寻找到的路径可视化for i, p in enumerate(path):if i == 0:maze[p[0]][p[1]] = "E"elif i == len(path) - 1:maze[p[0]][p[1]] = "S"else:maze[p[0]][p[1]] = 3print("\n")for r in maze:for c in r:if c == 3:print('\033[0;31m' + "*" + " " + '\033[0m', end="")elif c == "S" or c == "E":print('\033[0;34m' + c + " " + '\033[0m', end="")elif c == 2:print('\033[0;32m' + "#" + " " + '\033[0m', end="")elif c == 1:print('\033[0;;40m' + " " * 2 + '\033[0m', end="")else:print(" " * 2, end="")print()if __name__ == '__main__':maze = [[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1],[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1],[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],[1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1],[1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1],[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],[1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1],[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],[1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1],[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],[1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1],[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],[1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],[1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]]start = (0, 1)end = (24, 23)find_path(maze, start, end)see_path(maze, path)

NSSCTF [GDOUCTF 2023]润！

UPX壳但是是魔改过的upx壳,将FUK都改成UPX就好；再看就是正常的upx壳了，用upx -d

之后用IDA分析就好,直接反汇编来看主函数

init是创建迷宫，让我们输入长度为31的字符串，moving是在迷宫中的移动，这里的511是个hint

init点进去看看

这里具体迷宫的生成具体可以不用在意，可以明显看出这是一个 8 * 8大小的迷宫；

moving这里是三维的，还有上下楼这种操作。注意看：在case ‘u’:处又调用了一次init创建了一个迷宫，还有layer也是个hint，layer是层的意思，这里就是有八层。 8 * 8 * 8 ＝ 512 ；即意味着我们的终点就是左下角的位置，511；起点是一楼的左上角。我觉得难点就在这了，后面就按部就班。

哦还有，需要动态调试，输入uuuuuuuuuuuuuuuuuuuu就好，连续创建七次迷宫，将迷宫copy出来就好，4015CE下断点

x表示楼层，y是w和s表示行，z是列。

maze = [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 2]# maze[x * 64 + y * 8 + z]
def check_point_valid(map, x, y, z):if (x >= 0) and (x <= 7) and (y >= 0) and (y <= 7) and (z >= 0) and (z <= 7):return (map[x * 64 + y * 8 + z] != 1) and ((map[x * 64 + y * 8 + z] == 0) or (map[x * 64 + y * 8 + z] == 2))else:return Falsedef gen_nex(map, x, y, z):all_dir = []if check_point_valid(map, x - 1, y, z):all_dir.append((x - 1, y, z, 'n'))if check_point_valid(map, x + 1, y, z):all_dir.append((x + 1, y, z, 'u'))if check_point_valid(map, x, y - 1, z):all_dir.append((x, y - 1, z, 'w'))if check_point_valid(map, x, y + 1, z):all_dir.append((x, y + 1, z, 's'))if check_point_valid(map, x, y, z - 1):all_dir.append((x, y, z - 1, 'a'))if check_point_valid(map, x, y, z + 1):all_dir.append((x, y, z + 1, 'd'))return all_dirdef check_success(map, x, y, z):if map[x * 64 + y * 8 + z] == 2:return Trueelse:return Falsedef dfs(mapb, x, y, z, path):map = mapb.copy()if map[x * 64 + y * 8 + z] != 2:map[x * 64 + y * 8 + z] = 1if check_success(map, x, y, z):print(path)return Truenext_point = gen_nex(map, x, y, z)for n in next_point:pathn = path + n[3]dfs(map, n[0], n[1], n[2], pathn)outpus = ""
dfs(maze, 0, 0, 0,  outpus)

BUUCTF：[HDCTF2019]Maze

前面正常的upx32，脱壳

进去发现函数不完整，解析也出现错误，分析一下有花指令的干扰，直接去花

花指令，nop掉他！这里call直接nop就好

nop完后，全选红色的地址用p键得到main函数，再次反编译

现在就是找地图了，查看字符串

没有找到迷宫的规模在哪里，结合一共有70个字符，而且一共走了14步，asc_408078 = 5，dword_40807C = -4，可以大概猜出 7 * 10 的迷宫大小。

可知起始：408078=7 40807c=0（即+（7，0）），结束：408078=5 40807c=-4（F（5，-4）），画出地图。（a:左,s:下,d:右,w:上）

EXP:

map = ['*', '*', '*', '*', '*', '*', '*', '+', '*', '*', '*', '*', '*', '*', '*', '*', '*', ' ', '*', '*', '*', '*', '*', '*', ' ', ' ', ' ', ' ', '*', '*', '*', '*', ' ', ' ', ' ', '*', '*', '*', '*', '*', '*', '*', ' ', '*', '*', 'F', '*', '*', '*', '*', '*', '*', ' ', ' ', ' ', ' ', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*']# 添加限制条件
def check(map, x, y):if (x >= 0) and (x <= 7) and (y >= 0) and (y <= 9):    # 这一行检查(x,y)是否在有效范围内；return (map[10 * x + y] != '*') and ((map[10 * x + y] == ' ') or (map[10 * x + y] == 'F')) 	# 这里是如果坐标在地图范围内，就检测该坐标是不是障碍物；是不是可以前进的道路或者终点；else:return Falsedef gen_nex(map, x, y):all_dir = []if check(map, x - 1, y):all_dir.append((x - 1, y, 'w'))if check(map, x + 1, y):all_dir.append((x + 1, y, 's'))if check(map, x, y - 1):all_dir.append((x, y - 1, 'a'))if check(map, x, y + 1):all_dir.append((x, y + 1, 'd'))return all_dir
# all_dir是一个列表，用于存储下一个可能的坐标和前进方向的信息。每个元素都是一个包含三个值的元组，格式如下：(x, y, direction)def check_success(map, x, y):if map[10 * x + y] == 'F':return Trueelse:return Falsedef dfs(maze, x, y, path):map = maze.copy()    # 这里用将maze复制给map，避免修改掉原地图。if map[10 * x + y] != 'F':map[10 * x + y] = 1if check_success(map, x, y):print(path)return Truenext_point = gen_nex(map, x, y)for n in next_point:pathn = path + n[2]       # 将all_dir列表中的元组的第三个值，即方向传给pathndfs(map, n[0], n[1], pathn)        # 这里开始递归 用all_dir的元组第一二个值和pathn作为参数，进行当前位置的又一次深度优先遍历。output = ""
dfs(map, 0, 7, output)

2019华南师大CTF新生赛maze

题目地址：https://github.com/scnu-sloth/hsctf-2019-freshmen

找走迷宫的规则和方法，点开check函数看到

分析可知：这是一个含14*12的迷宫；'*'是迷宫的墙；'#'是迷宫终点

d为向右走一步；s为向右13步，在本二维数组中为向左下方一步或向右13步；w为向右上方一步或向左13步；a为向左一步

exp，直接借用了师傅BSF的算法:

#include<bits/stdc++.h>
using namespace std;
char mp[12*15];
int vis[12*15];
int dir[4]={1,-1,13,-13};
char S[4]={'d','a','s','w'};
struct node
{int x;string s;
};
queue<node> Q;
void bfs()
{node tmp;tmp.x=15;tmp.s="";Q.push(tmp);while(!Q.empty()){node now=Q.front();Q.pop();vis[now.x]=1;if(mp[now.x]=='#'){cout<<"flag{"<<now.s<<"}"<<endl;return;}for(int k=0;k<4;k++){int ux=now.x+dir[k];if(ux<1||ux>168||mp[ux]=='X'||vis[ux]==1)continue;tmp.x=ux;tmp.s=now.s+S[k];Q.push(tmp);}}
}
int main()
{int t=0;for(int i=1;i<=12;i++){for(int j=1;j<=14;j++){cin>>mp[++t];}}memset(vis,0,sizeof(vis));bfs();return 0;
}

还有突然发现了169 个字符，不就是 13 的平方，发现了13*13也对，上下左右就出来了，直接画个图就可以手解

flag{sssssdsssddsdddwwdwwaaaw}

攻防世界新手区 NJUPT CTF 2017 maze

64位ELF文件，无壳，先扔入IDA中查看伪代码

分析代码：

  puts("Input flag:");scanf("%s", &input_flag, 0LL);if ( strlen(&input_flag) != 24 || strncmp(&input_flag, "nctf{", 5uLL) || *(&byte_6010BF + 24) != '}' )		//这里要求输入的flag是24个字符，且前5个和最后一个都确定了{
LABEL_22:puts("Wrong flag!");exit(-1);}v3 = 5LL;if ( strlen(&input_flag) - 1 > 5 )		 {while ( 1 ){singleflag = *(&input_flag + v3);         // 这里v3是从5开始递增的数，目的是从第5个字符开始判断是否符合下述条件v5 = 0;if ( singleflag > 78 )	//这里给个范围，ASCII码大于78的划为第一类{singleflag = (unsigned __int8)singleflag;if ( (unsigned __int8)singleflag == 'O' )//如果第一个取O{v6 = sub_400650((_DWORD *)&v9 + 1);   goto LABEL_14;}if ( singleflag == 'o' )//如果第一个取o{v6 = sub_400660((int *)&v9 + 1);      // 有符号32位高字节操作，r15寄存器goto LABEL_14;}}else{singleflag = (unsigned __int8)singleflag;if ( (unsigned __int8)singleflag == '.' )//如果取到.{v6 = sub_400670(&v9);                 // 无符号底字节32位操作，r14寄存器goto LABEL_14;}if ( singleflag == '0' ){v6 = sub_400680((int *)&v9);          // 有符号底字节32位，r14寄存器
LABEL_14:v5 = v6;goto LABEL_15;}}
LABEL_15:if ( !(unsigned __int8)sub_400690((__int64)asc_601060, SHIDWORD(v9), v9) )goto LABEL_22;if ( ++v3 >= strlen(&input_flag) - 1 )   //在flag范围内v3加1，对应前面singleflag取第6、7、8~个一个个比较{if ( v5 )		//如果flag取完了，且sub_这些函数没有返回flase，也就是没有越界，就可以判断是否抵达终点了break;
LABEL_20:v7 = "Wrong flag!";goto LABEL_21;}}}if ( asc_601060[8 * (signed int)v9 + SHIDWORD(v9)] != '#' )	  //判断是否为#这个终点。goto LABEL_20;v7 = "Congratulations!";
LABEL_21:puts(v7);return 0LL;
}

由伪代码可见，这是个8*8的迷宫，有四个判断条件，分别进入了四个函数。
‘O’,‘o’,‘0’,’.'这四个字符分别控制不同方向
O左，o右，0下，.上
四个方向函数如下

bool __fastcall sub_400650(_DWORD *a1)//O
{int v1; // eaxv1 = (*a1)--;//向左一步return v1 > 0;//防止越界
}

bool __fastcall sub_400660(int *a1)//o
{int v1; // eaxv1 = *a1 + 1;//向右一步*a1 = v1;return v1 < 8;
}

bool __fastcall sub_400670(_DWORD *a1)//.
{int v1; // eaxv1 = (*a1)--;//向上一步return v1 > 0;
}

bool __fastcall sub_400680(int *a1)//0
{int v1; // eaxv1 = *a1 + 1;*a1 = v1;//向下一步return v1 < 8;
}

怎么分辨v9和v10各自控制的是上下还是左右呢？
点开sub_400690函数，看到

__int64 __fastcall sub_400690(__int64 a1, int a2, int a3)
{//a1是数组的首地址，a2是v10,a3是v9__int64 result; // raxresult = *(unsigned __int8 *)(a1 + a2 + 8LL * a3);//a3乘以8表明v9在二维数组中表示上下LOBYTE(result) = (_DWORD)result == ' ' || (_DWORD)result == '#';return result;
}

得知v9表示行，就是控制上下。v10表示列，就是控制左右。
而且只有‘ ’ 和#可以走，否则返回return 0。’*'是迷宫的墙。
写代码生成迷宫，0可走，X为墙。

找到类似迷宫的字符串

exp：

import numpy as np
q='nctf{'
h='}'
asc='  *******   *  **** * ****  * ***  *#  *** *** ***     *********'
mg=np.array(list(asc))
print(str(mg.reshape(int(len(asc)/8),8)).replace('\'',''))
# [[    * * * * * *]
#  [*       *     *]
#  [* * *   *   * *]
#  [* *     *   * *]
#  [*     * #     *]
#  [* *   * * *   *]
#  [* *           *]
#  [* * * * * * * *]]
mid_str='右下右右下下左下下下右右右右上上左左'.replace('上','.').replace('下','0').replace('左','O').replace('右','o')
print(q+mid_str+h)

BUUCTF：不一样的flag

拖进IDA查看main函数

int __cdecl __noreturn main(int argc, const char **argv, const char **envp)
{char v3[29]; // [esp+17h] [ebp-35h] BYREFint v4; // [esp+34h] [ebp-18h]int v5; // [esp+38h] [ebp-14h] BYREFint i; // [esp+3Ch] [ebp-10h]_BYTE v7[12]; // [esp+40h] [ebp-Ch] BYREF__main();v4 = 0;strcpy(v3, "*11110100001010000101111#");//这就是迷宫while ( 1 ){puts("you can choose one action to execute");puts("1 up");puts("2 down");puts("3 left");printf("4 right\n:");//控制方向scanf("%d", &v5);if ( v5 == 2 ){++*(_DWORD *)&v3[25];}else if ( v5 > 2 ){if ( v5 == 3 ){--v4;}else{if ( v5 != 4 )
LABEL_13:exit(1);++v4;}}else{if ( v5 != 1 )goto LABEL_13;--*(_DWORD *)&v3[25];}for ( i = 0; i <= 1; ++i ){if ( *(int *)&v3[4 * i + 25] < 0 || *(int *)&v3[4 * i + 25] > 4 )exit(1);}if ( v7[5 * *(_DWORD *)&v3[25] - 41 + v4] == '1' )exit(1);//是个5*5的迷宫且1为墙if ( v7[5 * *(_DWORD *)&v3[25] - 41 + v4] == '#' ){//‘#’是迷宫终点puts("\nok, the order you enter is the flag!");exit(0);}}
}

显然是一道迷宫题。
1，2，3，4分别控制上下左右

走迷宫即可

参考资料：

迷宫问题 - CTF Wiki (ctf-wiki.org)

bugku上一道迷宫逆向题的分析 - 『脱壳破解区』 - 吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

逆向迷宫题总结（持续更新） 2020华南师大CTF新生赛maze，攻防世界新手区：NJUPT CTF 2017，BUUCTF：不一样的flag_ctf lostmaze-CSDN博客

CTF-Reverse 迷宫地图类题目分析‘‘DFS和BFS算法‘‘（学习笔记）【详】_ctf 迷宫-CSDN博客【2021.12.28】ctf逆向中的迷宫问题（含exe及wp）_ctf迷宫-CSDN博客CTF-Reverse 迷宫地图类题目分析‘‘DFS和BFS算法‘‘（学习笔记）【详】_ctf 迷宫-CSDN博客

[算法]搜索初步: 从迷宫最短路问题来理解DFS和BFS · Issue #14 · Locietta/blogs (github.com)

【bugku】【ZSCTF】【迷宫RE】Take The Maze WriteUp - Reddest - 博客园 (cnblogs.com)