Python搜索算法 | ISCTF2024 | Reverse《回忆安魂曲》--第三章：逃不出的黑墙

undefined2024年12月10日约 673 字大约 2 分钟

将文件拖入 IDA 分析可得以下内容

可以从中提取出迷宫的字符串。

根据这里可以判断字符串是一个(31*30)-1的一个矩形。

大概是这种构造。

我们需要编写算法，使得从 P 点触发，不经过 C 直接到达 E（如果到达 C 点会触发彩蛋）

import hashlib
import numpy as np
from queue import Queue
from heapq import heappush, heappop

maze_str = """
###############################P#...............#...#.......#.#####.###.#####.#.###.#####.#.....#...#.#.....#...#.#...#.#####.#.###.#.#######.#.#.###.#C..#.#.#...#.#...#...#.#.#...#.#.#.#.#.###.#.#.#.###.#.#.#.#.#.#.#.#...#...#.#.......#.#.#.###.#.###.#####.#########.###.#...#...#.....#.#.......#...#.#.#####.#####.#.#.#####.###.#...#...#...#...#...#...#.#...#.###.#.###.#.#######.#.#.#.#.#...#.#.#...#.#...#...#...#.#.###.#.#.#####.#.#.#.#######.###.#...#.....#...#.#.#...#.....#.#########.#####.#.###.#.###.#.#.....#.#...#...#...#...#.#.#.#.#.#.#.###.#.#####.###.#.#.#...#.#...#.#...#...#...#...#.#.###.###.#.#####.#.###.###.#.#...#.#.#.......#.#...#.#...#.#####.#.#######.#.#####.#.###.#...#.#.......#.#...#...#.#..E#.#.#.#.#######.###.#.#####.#.#.#...#.............#.....#.#.#.###############.#######.#.#.#.........#...#...#.....#...#.#.#######.#.#.#####.#.#######.#.......#...#.......#.........
"""

maze_str = '\n'.join([maze_str[i:i+31] for i in range(1, len(maze_str), 30)])

print(maze_str)

# Split the maze string into lines and remove empty lines
maze_lines = [line for line in maze_str.strip().split('\n') if line]

# Get dimensions
height = len(maze_lines)
width = len(maze_lines[0])

# Create numpy array
maze = np.zeros((height, width), dtype=int)

# Fill array and find special points
start = None
checkpoint = None
end = None

for i, line in enumerate(maze_lines):
    for j, char in enumerate(line):
        if char == '#':
            maze[i, j] = 1
        elif char == 'P':
            start = (i, j)
        elif char == 'C':
            checkpoint = (i, j)
        elif char == 'E':
            end = (i, j)

print("Maze array created with shape:", maze.shape)
print("Start position (P):", start)
print("Checkpoint position (C):", checkpoint)
print("End position (E):", end)


def get_direct_path(maze, start, end):
    rows, cols = maze.shape
    visited = set()
    q = Queue()
    q.put((start, []))  # (position, path)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    direction_names = ['上', '下', '左', '右']

    while not q.empty():
        (i, j), path = q.get()

        if (i, j) == end:
            print("找到直接路径！")
            print("路径步骤:", ' '.join(path))
            print("总步数:", len(path))
            direction_map = {'上': 'l', '下': 'o', '左': 'v', '右': 'e'}
            path_new = [direction_map[d] for d in path]
            print("路径(使用love):", ''.join(path_new))
            print("MD5:", hashlib.md5(''.join(path_new).encode()).hexdigest())
            return path

        if (i, j) in visited:
            continue

        visited.add((i, j))

        for idx, (di, dj) in enumerate(directions):
            ni, nj = i + di, j + dj
            if (0 <= ni < rows and 0 <= nj < cols and
                maze[ni, nj] != 1 and (ni, nj) not in visited and
                    (ni, nj) != checkpoint):
                q.put(((ni, nj), path + [direction_names[idx]]))

    print("未找到不经过检查点的路径")
    return None


direct_path = get_direct_path(maze, start, end)

将最优路线的 MD5 提交即可。