关于迷宫题的一些求解思路

关于迷宫题的一些求解思路
2023-11-16 17:52:29 Author: mp.weixin.qq.com(查看原文) 阅读量:4 收藏

Maze

Maze简介：

迷宫题在CTF游戏题中可以说是一种比较常见的题型。这类题型模拟了一个迷宫，要求选手找到从起点到终点的路径。

通常，选手需要通过输入四个键—W、A、S、D，来控制迷宫中的角色上下左右移动，当然这四个键有时也可能会有所变换。在解决这类题目时，最终的flag通常是由起点到终点的路径构成。

对于简单的迷宫题一般只要找到地图，就可以人工编写出对应迷宫题的flag，随着难度的增加，地图可能变得很大，或者需要解决多张地图组合而成的多维地图结构。

分析一个简单的Maze程序分析：

这里我们可以尝试编写一个简单的maze程序，如下定义了一个码表，地图大小为10*10的，为了#字符为这个地图的墙或者说陷阱，字符S为地图的起始点，字符E为地图的终点，*为地图中可以走的路径。

#include <stdio.h>
#include <stdlib.h>
char maze [100] = {
     '#', 'S', '#', '#', '#', '#', '#', '#', '#', '#',
     '#', '*', '*', '#', '#', '#', '#', '#', '#', '#',
     '#', '#', '*', '#', '#', '#', '#', '#', '#', '#',
     '#', '#', '*', '*', '#', '#', '#', '#', '#', '#',
     '#', '#', '#', '*', '#', '#', '#', '#', '#', '#',
     '#', '*', '*', '*', '#', '#', '#', 'E', '#', '#',
     '#', '*', '#', '#', '#', '#', '#', '*', '#', '#',
     '#', '*', '#', '#', '#', '#', '#', '*', '#', '#',
     '#', '*', '*', '*', '*', '*', '*', '*', '#', '#',
     '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'
};
int main() {
    int t = 1, i;
    char move[24];
    scanf_s(" %s", move, sizeof(move));
    for (i = 0; move[i];i++) {
        switch (move[i]) {
        case 'w': t -= 10; break;
        case 'a': t--; break;
        case 's': t += 10; break;
        case 'd': t++; break;
        default: continue;  // Invalid move, do nothing
        }
        if (maze[t] == '#') {
            printf("I'm sorry,The player is dead!");
            exit(1);
        }
        if (maze[t] == 'E') {
            printf("Congratulations, you've found the exit!\n");
                        printf("Flag is your Input\n");
        }
    }
    return 0;
}

程序要求将路径一次性输入，这里的for就是对输入的路径逐个进行判断，这里需要补充一个点，由于上面代码中的地图使用的是一维数组，所以下标针对上下操作时是直接加减列数，这个地方应该好理解。关于地图比较直观的显示当然还是用二维数组好一点，不过这个题作为入门题，使用一维数组有一个好处就是可以通过下标推测出地图的列数，关于这个点逆向分析完这个代码就可以大概理解。

二维数组的表示以及switch判断可以这么写：

#define SIZE 10
char maze[SIZE][SIZE] = {
    {'S', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
    {'#', '*', '*', '#', '#', '#', '#', '#', '#', '#'},
    {'#', '#', '*', '#', '#', '#', '#', '#', '#', '#'},
    {'#', '#', '*', '*', '#', '#', '#', '#', '#', '#'},
    {'#', '#', '#', '*', '#', '#', '#', '#', '#', '#'},
    {'#', '*', '*', '*', '#', '#', '#', 'E', '#', '#'},
    {'#', '*', '#', '#', '#', '#', '#', '*', '#', '#'},
    {'#', '*', '#', '#', '#', '#', '#', '*', '#', '#'},
    {'#', '*', '*', '*', '*', '*', '*', '*', '#', '#'},
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};
scanf(" %c", &move);
    switch(move) {
        case 'w': if (x > 0 && maze[x-1][y] != '#') x--; break;
        case 'a': if (y > 0 && maze[x][y-1] != '#') y--; break;
        case 's': if (x < SIZE-1 && maze[x+1][y] != '#') x++; break;
        case 'd': if (y < SIZE-1 && maze[x][y+1] != '#') y++; break;
        default: printf("Invalid move!\n");
    }

大概知道了maze程序大概是个啥样子之后将它编译成可执行程序，然后用ida打开看一下：

这就是程序反汇编之后的内容，可以看到maze类型的题目的特点，这类程序会有一个switch对四个方向进行相应的下标操作。接着关注到33行的v5加等10这条语句，通过这条语句就可以判断出地图每列一定是10个元素，接着就是找地图了，aSE很明显就是这个程序的地图：

找到地图之后将其提取出来进行手工整理，接着就能获得起点到终点的路径：

获得flag：sdssdssaasssddddddwww

通过对这个例子的分析此时对maze题已经有了一定的了解，下面从易到难分析几个实例。

实例闯关：

下面的示例会遇到逆向中其他的逆向技术比如去壳和去花等，这些知识点有些在前面的博客中写过，可以翻翻前面的几篇文章，这篇文章主要是分析maze题的解题思路，如果涉及了还没写过的知识点这里不会细讲，之后会单开文章。

实例一：Buuoj Maze：

拿到程序后先了解加壳情况以及程序的位数：

脱壳：

脱壳之后放到ida中发现加了花指令：

将其nop后按p识别函数然后f5反汇编就可以成功看到main函数了。

将反汇编后代码的符号稍作优化：

根据前面的经验我们需要找到地图以及地图的行列数，先尝试找找地图，发现主函数的逻辑没有地图相关的变量，怎么解决呢？

这里尝试shift+f12查找字符串：

可以看到上图的字符串就是地图。找到地图后继续找地图的行列数，之前我们判断行列数是通过switch里面对下标的加减来判断的，但是这个实例有点不同，他用了两个下标进行操作，也就是说一个下标对横坐标进行判定，一个下标对纵坐标进行判定，然后在下面的if直接对横纵坐标分别进行判定，到了这里我们就无法直观的推测出这个地图的行列数。

既然推测不出来那就干脆直接爆破出行列。首先提取出来的地图有70个字符，那么70除以列数肯定是可以整除的，首先写一个简单的脚本输出70的所有正因子。

list = []                #关于for的取值范围:
for i in range(5,36):    #1.伪代码的最后的if判断其中有个数要为5,所以行列必定大于5
    if 70%i == 0:        #2.一个数的因子不可能大于它的一半
        list.append(i)

通过得出来的值直接进行爆破：

for j in list:
    for i in range(len(maze)):
        print(maze[i],end='')
        if (i+1)%j==0:
            print()
    print('---------------------')

最后从脚本输出的结果中，下面这个是最正常的。

*******+**
******* **
**** **
** *****
** **F****
** ****
**********

这个地图依旧很小，直接手写出flag即可。

flag{ssaaasaassdddw}

实例二：BuuojOruga

main函数分析

这个程序没加壳直接放入ida。

__int64 __fastcall main(int a1, char **a2, char **a3)
{
  __int64 result; // rax
  int i; // [rsp+0h] [rbp-40h]
  char s1[6]; // [rsp+4h] [rbp-3Ch] BYREF
  char s2[6]; // [rsp+Ah] [rbp-36h] BYREF
  char s[40]; // [rsp+10h] [rbp-30h] BYREF
  unsigned __int64 v8; // [rsp+38h] [rbp-8h]
  v8 = __readfsqword(0x28u);
  memset(s, 0, 0x19uLL);
  printf("Tell me the flag:");
  scanf("%s", s);
  strcpy(s2, "actf{");
  for ( i = 0; i <= 4; ++i )
    s1[i] = s[i];
  s1[5] = 0;
  if ( !strcmp(s1, s2) )
  {
    if ( (unsigned __int8)sub_78A(s) )
      printf("That's True Flag!");
    else
      printf("don't stop trying...");
    result = 0LL;
  }
  else
  {
    printf("Format false!");
    result = 0LL;
  }
  return result;
}

第一个for循环是将输入的字串的前5个字符拿出来和“actf{”进行比较，配对成功则调用sub_78A()函数。

sub_78A分析：

_BOOL8 __fastcall sub_78A(__int64 a1)
{
  int v2; // [rsp+Ch] [rbp-Ch]
  int v3; // [rsp+10h] [rbp-8h]
  int v4; // [rsp+14h] [rbp-4h]
  v2 = 0;
  v3 = 5;
  v4 = 0;
  while ( byte_201020[v2] != 0x21 )
  {
    v2 -= v4;
    if ( *(_BYTE *)(v3 + a1) != 'W' || v4 == -16 )
    {
      if ( *(_BYTE *)(v3 + a1) != 'E' || v4 == 1 )
      {
        if ( *(_BYTE *)(v3 + a1) != 'M' || v4 == 16 )
        {
          if ( *(_BYTE *)(v3 + a1) != 'J' || v4 == -1 )
            return 0LL;
          v4 = -1;                              // J表示左移
        }
        else
        {
          v4 = 16;                              // M表示下移
        }
      }
      else
      {
        v4 = 1;                                 // E表示右移
      }
    }
    else
    {
      v4 = -16;                                 // W表示上移
    }
    ++v3;
    while ( !byte_201020[v2] )                  // 当前值为0则继续循环
    {
      if ( v4 == -1 && (v2 & 0xF) == 0 )        // 当前在最左边一列的时候，不能过左移
        return 0LL;
      if ( v4 == 1 && v2 % 16 == 15 )           // 当前在最右边一列的时候，不能够右移
        return 0LL;
      if ( v4 == 16 && (unsigned int)(v2 - 240) <= 0xF )// 在最后一行时，不能下移
        return 0LL;
      if ( v4 == -16 && (unsigned int)(v2 + 15) <= 0x1E )// 在第一行，不能上移
        return 0LL;
      v2 += v4;                  // 当值为0就一直移动，但要注意退出循环时一定已经处于不满
    }                            // 的状态所以对于走迷宫来说时多移动了一次，在12行做了一     
  }                              // 个往后退一步的处理
  return *(_BYTE *)(v3 + a1) == 125;
}

这里看到一个迷宫题的特征就是13到19行的四个字母，发现这个点后就去找地图，发现byte_201020里面的值：

通过v4要么加16，要么加1，和这个数组的大小为256可知，这是张16*16的地图，直接去Hex窗口里看：

大概是个这么个走法：

转换成字母就是：MEWEMEWJMEWJM

这个题目和前面程序的主要区别就是，前面分析的程序每次移动一个位置，而这个题目每次移动都会一直移动到撞墙才停止，实现这部分的代码为主函数的while循环，我在主函数上加了注释，可以理一理这个程序的思路。

实例三：Volga Quals CTF 2014: Reverse 100

◆题目附件

https://bbs.kanxue.com/Maze%207632b5439dec4ff4930308a213f1ab61/ciscn_2019_n_1.txt

把后缀去掉即可，下面的几个附件同理。

直接使用ida打开程序，主函数中很多字符串的内存赋值操作：

紧接着是一个while判断：

看到了四个if，分别判断了四个字符L、R、U、D，然后L、R影响的变量为pos_x；U、D影响的变量为pos_y。这个循环的作用就不用多说了，UDLR分别代表上下左右。pos_x表示行下标，pos_y表示列下标。这个题目很清晰，上面那一大堆字符串的内存赋值明显就是构成地图了。回到构成地图的代码处发现一个比较恶心的地方：

地图是一行一行复制到内存的，关键是打乱了顺序，每一行都有对应的行号，将地图提取出来后，需要按照行号恢复顺序，这里可以一次性将值提取出来后，写一个脚本恢复顺序虽然也没有方便到哪去。

maze = [
"**########################################################################################",
"#************######*##############**************##*####*#######*##*##*###*#####*####*#####",
"###*#########*****************************************************************############",
"###*#########*###############################################*######*****************#####",
"###**********#############################################################################",
"#*######################*******************************************#####*************#####",
"############*#####*******************************************************************#####",
"###*#################################################*#########*##*######*#####*####*#####",
"###*####*****#####**********************#############*#########*##********#####*####*#####",
"#************************####*####################################*#####*###########*#####",
"###*####*###*#####*############################################*****************####*#####",
"###*####*###*#####*####################***************#########*###############*####*#####",
"#########*#########*#########*#######***************************##*#####*###########*#####",
"#############################################################*######*#####################",
"#******##*#########*#########*#######*#########################*##*#####*###########*#####",
"#*####*##*#########*#########*#######*#########################*##*#####********####*#####",
"###******###*#####*#################################################################*#####",
"###*#########*###############################################*############################",
"#*####*##*#########*######*******####*###**********####****####*##*############*####*#####",
"#*##***#**#########*#################*###*########*####*#######*##*############*####*#####",
"###**************************************************########*######*#####################",
"#*##*###*##########*##############****###*******##*####*#######*##*##*****#####*####*#####",
"#*##*###*##########*##############*############*##*####*#######*##*##*###*#####*####*#####",
"###################*##############################*####***#####*##*##*###*#####*####*#####",
"###################********************************############*##*##*###*#####*####*#####",
"###############################################################*##*##*###*#####*####*#####",
"#########################*****************************************************************",
"###***************************************************#########*##*##*###*#####*####*#####",
"#############################################################*######*#####################",
"#*#######*####**###*#######***#######*########**###*******##*****##########################",
"##*#####*###*###*##*######*#########*#*######*##*#####*#####*##############################",
"###*###*####*###*##*######*##**####*###*####*#########*#####***############################",
"####*#*#####*###*##*##*###*###*###*******####*##*#####*#####*##############################",
"#####*#######**####****####**####*#######*####**######*#####*##############################"
]
list = [0, 10, 22, 24, 21, 1, 20, 15, 16, 2, 18, 17, 3, 26, 4, 5, 19, 23, 6, 7, 25, 8, 9, 11, 12, 13, 28, 14, 27, 29, 30, 31, 32, 33]
with open('maze.txt', 'w') as f:
# 遍历行号列表，将对应的字符串写入到文件中
for i in range(len(list)):
print(maze[list.index(i)], file=f)

上面的脚本将恢复顺序的地图输出到一个文件中，然后查看地图会发现这个地图还不小：

**########################################################################################
#*######################*******************************************#####*************#####
#************************####*####################################*#####*###########*#####
#########*#########*#########*#######***************************##*#####*###########*#####
#******##*#########*#########*#######*#########################*##*#####*###########*#####
#*####*##*#########*#########*#######*#########################*##*#####********####*#####
#*####*##*#########*######*******####*###**********####****####*##*############*####*#####
#*##***#**#########*#################*###*########*####*#######*##*############*####*#####
#*##*###*##########*##############****###*******##*####*#######*##*##*****#####*####*#####
#*##*###*##########*##############*############*##*####*#######*##*##*###*#####*####*#####
#************######*##############**************##*####*#######*##*##*###*#####*####*#####
###################*##############################*####***#####*##*##*###*#####*####*#####
###################********************************############*##*##*###*#####*####*#####
###############################################################*##*##*###*#####*####*#####
###***************************************************#########*##*##*###*#####*####*#####
###*#################################################*#########*##*######*#####*####*#####
###*####*****#####**********************#############*#########*##********#####*####*#####
###*####*###*#####*####################***************#########*###############*####*#####
###*####*###*#####*############################################*****************####*#####
###******###*#####*#################################################################*#####
############*#####*******************************************************************#####
###**********#############################################################################
###*#########*****************************************************************############
###*#########*###############################################*############################
###*#########*###############################################*######*****************#####
###**************************************************########*######*#####################
#############################################################*######*#####################
#############################################################*######*#####################
#########################*****************************************************************
#*#######*####**###*#######***#######*########**###*******##*****#########################
##*#####*###*###*##*######*#########*#*######*##*#####*#####*#############################
###*###*####*###*##*######*##**####*###*####*#########*#####***###########################
####*#*#####*###*##*##*###*###*###*******####*##*#####*#####*#############################
#####*#######**####****####**####*#######*####**######*#####*#############################

碰到这种大地图一个一个手写方向会非常麻烦，这时候就要引入一个知识点：利用BFS算法寻找最短路径，如果对这个算法不是很熟悉的话可以看我的上一篇文章，搞定这个知识点，最好是自己写一个脚本出来以后碰到类似问题就可以改改数据直接用。下面是这个题的BFS脚本：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
char maze[34][91] = {
    "S*########################################################################################",
    "#*######################*******************************************#####*************#####",
    "#************************####*####################################*#####*###########*#####",
    "#########*#########*#########*#######***************************##*#####*###########*#####",
    "#******##*#########*#########*#######*#########################*##*#####*###########*#####",
    "#*####*##*#########*#########*#######*#########################*##*#####********####*#####",
    "#*####*##*#########*######*******####*###**********####****####*##*############*####*#####",
    "#*##***#**#########*#################*###*########*####*#######*##*############*####*#####",
    "#*##*###*##########*##############****###*******##*####*#######*##*##*****#####*####*#####",
    "#*##*###*##########*##############*############*##*####*#######*##*##*###*#####*####*#####",
    "#************######*##############**************##*####*#######*##*##*###*#####*####*#####",
    "###################*##############################*####***#####*##*##*###*#####*####*#####",
    "###################********************************############*##*##*###*#####*####*#####",
    "###############################################################*##*##*###*#####*####*#####",
    "###***************************************************#########*##*##*###*#####*####*#####",
    "###*#################################################*#########*##*######*#####*####*#####",
    "###*####*****#####**********************#############*#########*##********#####*####*#####",
    "###*####*###*#####*####################***************#########*###############*####*#####",
    "###*####*###*#####*############################################*****************####*#####",
    "###******###*#####*#################################################################*#####",
    "############*#####*******************************************************************#####",
    "###**********#############################################################################",
    "###*#########*****************************************************************############",
    "###*#########*###############################################*############################",
    "###*#########*###############################################*######*****************#####",
    "###**************************************************########*######*#####################",
    "#############################################################*######*#####################",
    "#############################################################*######*#####################",
    "#########################****************************************************************E",
    "#*#######*####**###*#######***#######*########**###*******##*****#########################",
    "##*#####*###*###*##*######*#########*#*######*##*#####*#####*#############################",
    "###*###*####*###*##*######*##**####*###*####*#########*#####***###########################",
    "####*#*#####*###*##*##*###*###*###*******####*##*#####*#####*#############################",
    "#####*#######**####****####**####*#######*####**######*#####*#############################"
};
struct Point {
    int row, col;
    string path;  // 路径跟踪变量
};
bool isValid(int row, int col) {
    // 检查点是否在地图内并且是可行走的
    return row >= 0 && row < 34 && col >= 0 && col < 91 && maze[row][col] != '#';
}
void bfs() {
    queue<Point> q;
    q.push({ 0, 0, "" });  // 将起点放入队列中
    bool visited[34][91] = { false };
    visited[0][0] = true;  // 该变量用于记录图中的每个节点是否已被访问过
    while (!q.empty()) {
        Point p = q.front();
        q.pop();
        int row = p.row;
        int col = p.col;
        string path = p.path;
        // 判断是否到终点了
        if (maze[row][col] == 'E') {
            cout << path << endl;
            return;
        }
        // 检查每个方向，如果有效就排队
        if (isValid(row - 1, col) && !visited[row - 1][col]) {
            q.push({ row - 1, col, path + 'U' });
            visited[row - 1][col] = true;
        }
        if (isValid(row + 1, col) && !visited[row + 1][col]) {
            q.push({ row + 1, col, path + 'D' });
            visited[row + 1][col] = true;
        }
        if (isValid(row, col - 1) && !visited[row][col - 1]) {
            q.push({ row, col - 1, path + 'L' });
            visited[row][col - 1] = true;
        }
        if (isValid(row, col + 1) && !visited[row][col + 1]) {
            q.push({ row, col + 1, path + 'R' });
            visited[row][col + 1] = true;
        }
    }
    cout << "No path found" << endl;
}
int main() {
    bfs();
    return 0;
}

实例四：SCTF2019 babygame

◆题目附件

https://bbs.kanxue.com/Maze%207632b5439dec4ff4930308a213f1ab61/babygame.txt

这个题目的考察的知识点不少，地图只是其中一个小的知识点，具体题解可以看博客中的wp复现模块，这里只是将其中的迷宫考点单独拎出来讲。首先看一下去完花指令后的主函数maze部分代码：

代码中可以直接看到地图字符串，但是观察switch语句，这里判断了六个字符前面的wasd四个字符都好理解也就是上下左右，但是后面的xy就显得十分突兀，一般的地图就只需要走四个方向，这里为啥会有六个字符呢？

这里的地图其实是一张三维地图，不知道各位有没有玩过魔塔这个十分古早的单击游戏，玩家扮演勇士的角色，从塔的第一层开始打怪升级，然后进入第二层继续打怪升级。这就是三维地图，x表示去到上层地图，y表示去到下层地图。也就是说这张地图实际是由五张五乘五的地图构成。

{'*','*','*','*','*'}
{'*','*','*','*','*'}
{'*','*','*','*','.'}
{'*','*','*','*','.'}
{'*','*','s','.','.'}

{'*','*','*','*','*'}
{'*','*','*','*','*'}
{'*','*','*','*','*'}
{'*','*','*','*','*'}
{'.','*','*','.','.'}

{'*','.','.','*','*'}
{'*','*','*','*','.'}
{'*','*','*','*','.'}
{'*','*','*','*','*'}
{'*','*','*','*','*'}

{'*','*','*','*','*'}
{'*','*','.','.','*'}
{'*','.','.','.','*'}
{'.','.','*','.','*'}
{'.','*','*','.','*'}

{'*','.','.','*','*'}
{'*','.','.','*','*'}
{'.','.','#','*','.'}
{'.','*','*','*','.'}
{'.','*','*','*','.'}

根据题目的输出提示需要找到最短的路径，还是使用BFS算法进行查找，之前的代码依然能用，不过要稍作修改，修改时需要注意的地方有：

◆定义的结构体需要多加一个坐标。

◆在循环中还需要添加一个变量来表示不同层

具体的代码如下：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
char maze[5][5][5] = {
    {
        {'*','*','*','*','*'},
        {'*','*','*','*','*'},
        {'*','*','*','*','.'},
        {'*','*','*','*','.'},
        {'*','*','s','.','.'},
    },                       
    {                        
        {'*','.','.','*','*'},
        {'*','*','*','*','.'},
        {'*','*','*','*','.'},
        {'*','*','*','*','*'},
        {'*','*','*','*','*'},
    },                       
    {                        
        {'*','.','.','*','*'},
        {'*','.','.','*','*'},
        {'.','.','#','*','.'},
        {'.','*','*','*','.'},
        {'.','*','*','*','.'},
    },                       
    {                        
        {'*','*','*','*','*'},
        {'*','*','*','*','*'},
        {'*','*','*','*','*'},
        {'*','*','*','*','*'},
        {'.','*','*','.','.'},
    },                       
    {                        
        {'*','*','*','*','*'},
        {'*','*','.','.','*'},
        {'*','.','.','.','*'},
        {'.','.','*','.','*'},
        {'.','*','*','.','*'}
    }
};
struct Point {
    int layer, row, col;
    string path;  // 路径跟踪变量
};
bool isValid(int layer, int row, int col) {
    // 检查点是否在地图内并且是可行走的
    return layer >= 0 && layer < 5 && row >= 0 && row < 5 && col >= 0 && col < 5 && maze[layer][row][col] != '*';
}
void bfs() {
    queue<Point> q;
    q.push({ 0, 4, 2, "" });  // 将起点放入队列中
    bool visited[5][5][5] = { false };
    visited[0][0][0] = true;  // 该变量用于记录图中的每个节点是否已被访问过
    while (!q.empty()) {
        Point p = q.front();
        q.pop();
        int layer = p.layer;
        int row = p.row;
        int col = p.col;
        string path = p.path;
        // 判断是否到终点了
        if (maze[layer][row][col] == '#') {
            cout << path << endl;
            return;
        }
        // 检查每个方向，如果有效就排队
        if (isValid(layer, row - 1, col) && !visited[layer][row - 1][col]) {
            q.push({ layer, row - 1, col, path + 'w' });
            visited[layer][row - 1][col] = true;
        }
        if (isValid(layer, row + 1, col) && !visited[layer][row + 1][col]) {
            q.push({ layer, row + 1, col, path + 's' });
            visited[layer][row + 1][col] = true;
        }
        if (isValid(layer, row, col - 1) && !visited[layer][row][col - 1]) {
            q.push({ layer, row, col - 1, path + 'a' });
            visited[layer][row][col - 1] = true;
        }
        if (isValid(layer, row, col + 1) && !visited[layer][row][col + 1]) {
            q.push({ layer, row, col + 1, path + 'd' });
            visited[layer][row][col + 1] = true;
        }
        if (isValid(layer - 1, row, col) && !visited[layer - 1][row][col]) {
            q.push({ layer - 1, row, col, path + 'y' });
            visited[layer - 1][row][col] = true;
        }
        if (isValid(layer + 1, row, col) && !visited[layer + 1][row][col]) {
            q.push({ layer + 1, row, col, path + 'x' });
            visited[layer + 1][row][col] = true;
        }
    }
    cout << "No path found" << endl;
}
int main() {
    bfs();
    return 0;
}

实例五：2021巅峰极客baby_maze

◆题目附件

https://bbs.kanxue.com/Maze%207632b5439dec4ff4930308a213f1ab61/maze.txt

先尝试运行程序：

根据题目输出，可以知道这个地图是正常的走东南西北四个方向，第一步是向南走。把程序丢入ida中。根据字符串地位到接收第一步向南字符“S”的函数：

可以看到只有输入S字符才能进入下一步函数step_1，继续跟踪step_1函数：

这个函数很简单，接收一个新的字符然后对其进行判断，输入‘A’，‘D’都会显示遇到了怪物，但是程序不会退出而是等待我们重新输入当前这个位置的方向字符，输入‘W’就退回到上一个函数，只有输入‘S’才能继续到下一个函数。到这里就发现有点不对劲了，和之前分析的几个程序不同，前面的程序判断完有几个方向之后就开始找地图字符串了，这个程序没得地图，它不是一次性接收所有路径然后进行判断，而是一次接收一个字符，用一个一个函数来对当前路径进行判断，而且继续往下跟踪会发现这个迷宫不只有一条路，在有些地方是有分叉路的。我这里尝试一个函数一个函数的走发现一个问题，根本走不完，函数太多了。所以这里我们不得不换一个思路了。

根据目前的发现可以提取到如下信息：

◆程序没有地图字符串。

◆走错方向并不会退出程序，而是停在当前位置等待重新输入。

◆在遇到分支路口时即使走错了也可以通过往反方向走回溯到分支路口。

◆程序对每次输入都会有相应的信息输出，来表明是否走对了。

根据已有的信息，首先可以考虑使用pwntools实现程序交互，再使用BFS或者DFS来对地图进行遍历。大致思路为：

sh = process("./maze")
sh.recvuntil("This is the beginning. You can only go south.\n")
sh.send(b'S')

先发送一个‘S’字符过去，然后利用sh接收程序的返回信息：

temp = sh.recvuntil('\n')

然后根据返回的信息，来判断是否走对了。

if temp == b'OUCH!!!!\n' or temp == b'I can\'t see the sky\n' or temp == b'Shit!!\n' or temp == b'Wall!!!\n' or temp == b'Fxxk!!!\n' or temp == b'nononononono\n' or temp == b'Uh... yeah, no.\n' or temp == b'Oh!!Monster\n' or temp == b'Maybe this is a mistack\n' or temp == b'Oh no!!!\n' or temp == b'Let me out!!!\n':

这里依然要注意就是这里的判断需要循环判断直到找到正确的方向为止，然后就是并不是判断四个方向，来的那条路的反方向就不用管了。比如我是输入‘S’到的下一个函数，那就不用判断’W‘了，因为输入‘W’字符后程序依然会返回正确的字符串提示，这会让脚本无法区分，这里可以加上一个判断。

opposite = {
    b'W': b'S',
    b'A': b'D',
    b'D': b'A',
    b'S': b'W'
}
if t!= opposite[path-1]]:
            payload += direct[i]

其中表示当前判断的方向。

做完这些前置操作后，然后我们需要判断是使用BFS算法还是DFS算法来对迷宫路径进行求解。

首先分析一下当前场景由于这是一个交互式的程序每次的步进都表示着与不同函数的交互，我们编写的脚本需要有一个东西能记录当前的路径走向，以便在走错路时回溯到分支路口。

对于特定的应用场景中，我们就需要更多的关注DFS和BFS针对撤销和回溯这两个操作的可行性。

1.撤销操作：在DFS中，当你沿着一个方向前进但最终碰到一个障碍时，你可以简单地从栈中弹出一个元素，然后尝试下一个方向。但在BFS中，你会探索所有可能的邻居，然后再探索这些邻居的邻居，所以你不能简单地“撤销”一个操作，因为你会丢失对其他邻居的引用。

2.路径回溯：在DFS中，当前的路径是通过栈来实时维护的，这使得回溯变得非常直观。在BFS中，尽管可以通过从目标点反向遍历父映射来重建路径，但这并不意味着可以轻松地“撤销”或“回溯”BFS中的单个操作。

简单点说就是由于DFS的递归和深入探索策略，它更容易实现撤销操作。当DFS探索一个不成功的路径时，它会自然地返回到上一个决策点，这与撤销操作的思想完美地契合。所以DFS算法更适合这个程序的路径寻找。

下面是一开始写的解决方案：

from pwn import *
context(os='linux', arch='amd64', log_level='info')
sh = process("./maze")
direct = [b'W', b'A', b'S', b'D']
opposite = {
    b'W': b'S',
    b'A': b'D',
    b'D': b'A',
    b'S': b'W'
}
success = [
    b'Just do it\n',
    b'GOGOGO\n',
    b'Wuhu~!\n',
    b'Wuhu\n',
    b'You are so good\n',
    b'Nice.\n',
    b'Yeah~~\n',
    b'Yeah~~~\n',
    b'Let\'s go.\n',
    b'Never stop\n',
    b'So smart\n',
]
sh.recvuntil(b"This is the beginning. You can only go south.\n")
sh.send(b'S')
sh.recvuntil(b'\n')
def dfs(path, depth):
    for i in direct:
        if i == opposite[path[-1:]]:
            continue
        sh.send(i)
        feedback = sh.recvuntil(b'\n')
        if feedback == b"Good Job. \n":
            print("I find it!!!")
            print(path+i)
            return
        if feedback in success:
            print(path+i)
            dfs(path + i, depth + 1)
        #
        sh.send(opposite[i])  # move back
        sh.recvuntil(b'\n')
dfs(b'S',1)

但是运行到一半报错了，这里使用的是递归算法，然后一层一层向下走：

查看了一下报错信息，发现是超过了python默认的最大递归层级，所以需要转变一下代码逻辑，我们可以创建一个文件来记录已经走出来的路径，然后循环打开迷宫程序，之前走过的路利用一个循环来直接输入到程序，然后继续寻找之后的路径，这样循环往复就可以避免递归超出递归层级的情况。

from pwn import *
context(arch='amd64',os='linux',log_level='info')
direc = [b'W',b'S',b'A',b'D']
anti_direc = [b'S',b'W',b'D',b'A']
payload = b'SSSSSSSSSDDDDDDWWWWAAWWAAWWDDDDDDDDDDDDDDDDDDDDSSDDSSAASSSSAAAAWWAAWWWWAASSSSSSAASSDDSSSSDDWWWWDDSSDDDDWWDDDDDDWWAAAAWWDDDDWWAAWWWWDD'
def DFS(payload,length):
    if length ==480:
        F = open('pay.txt','a+')
        F.write(str(payload) + '\n')
        F.close()
        return 0
    print(payload)
    p = process('./maze')
    p.recvuntil('south.\n')
    p.sendline(payload)
    for i in range(0,length-1):
        p.recvuntil('\n')
    temp = p.recvuntil('\n')
    print(temp)
    if temp == b'OUCH!!!!\n' or temp == b'I can\'t see the sky\n' or temp == b'Shit!!\n' or temp == b'Wall!!!\n' or temp == b'Fxxk!!!\n' or temp == b'nononononono\n' or temp == b'Uh... yeah, no.\n' or temp == b'Oh!!Monster\n' or temp == b'Maybe this is a mistack\n' or temp == b'Oh no!!!\n' or temp == b'Let me out!!!\n':
        p.close()
        print('WRRONG !!! -----',payload)
        return 0
    if temp == b'Good Job. \n':
        F=open('map.txt','a')
        p.close()
        for i in range(100):
            F.write(str(payload) + '\n')
        F.close()
        return 0
    p.close()
    print('------------------------------')
    t = payload[length-1:length]
    for i in range(0,4):
        if t!= anti_direc[i]:
            payload += direc[i]
            DFS(payload,len(payload))
            payload = payload[0:len(payload)-1]
DFS(payload,len(payload))

以上就是我个人关于迷宫题题型的一些收集，上面这个例子应该还有更好的解法，这个方法还是比较笨的，脚本跑下来也要不少时间。

看雪ID：宇宙大魔王

https://bbs.kanxue.com/user-home-920613.htm

*本文为看雪论坛优秀文章，由宇宙大魔王原创，转载请注明来自看雪社区

# 往期推荐

1、IOFILE exploit入门

2、入门编译原理之前端体验

3、如何用纯猜的方式逆向喜马拉雅xm文件加密(wasm部分)

4、反恶意软件扫描接口(AMSI)如何帮助您防御恶意软件

5、sRDI — Shellcode反射式DLL注入技术

6、对APP的检测以及参数计算分析

球分享

球点赞

球在看

文章来源: https://mp.weixin.qq.com/s?__biz=MjM5NTc2MDYxMw==&mid=2458528628&idx=1&sn=ef9ac6ebbb41e22a4fa4b62bf1a9bd49&chksm=b18d1bfe86fa92e8d3ee8a6e5ea85ee6cc59e3feffb769ac66fb3a5e5dcb252c99bc87239a3a&scene=58&subscene=0#rd
如有侵权请联系:admin#unsafe.sh