前言：
不得不说，随着时间的推移，CTF也越来越卷了，当初的新生赛都是些xor upx 迷宫之类的，现在的新生赛连vm都上去了，所以真的是新生们在做题吗？
1.[2019UNCTF] easyvm
第一次做vm题，啥也不会，翻阅了好几篇wp才清楚一点吧...
分析一下：有个关键函数sub_400C1E，然后判断长度是否为32，下面一个unk_602080,unk_6020A0
我们先看一下这两个unk
这个里面就是opcode(操作码)
这个应该就是给的密文了
先分析一下sub_400C1E这个函数
发现a1与一些偏移量，看看a1是什么
都是些未知函数，那么显然，该vm就是通过a1进行取址然后调用函数，对栈空间，寄存器之类的东西进行操控
__int64 __fastcall sub_400806(__int64 a1, __int64 opcode, __int64 a3, __int64 a4)
{
*(a1 + 8) = opcode + 9;
*(a1 + 24) = a3;
*(a1 + 32) = a4;
while ( 2 )
{
switch ( **(a1 + 8) )
{
case 0xA0:
(*(*a1 + 8LL))(a1);
continue;
case 0xA1:
(*(*a1 + 16LL))(a1);
continue;
case 0xA2:
(*(*a1 + 24LL))(a1);
*(a1 + 8) += 11LL;
continue;
case 0xA3:
(*(*a1 + 32LL))(a1);
*(a1 + 8) += 2LL;
continue;
case 0xA4:
(*(*a1 + 40LL))(a1);
*(a1 + 8) += 7LL;
continue;
case 0xA5:
(*(*a1 + 48LL))(a1);
++*(a1 + 8);
continue;
case 0xA6:
(*(*a1 + 56LL))(a1);
*(a1 + 8) -= 2LL;
continue;
case 0xA7:
(*(*a1 + 64LL))(a1);
*(a1 + 8) += 7LL;
continue;
case 0xA8:
(*(*a1 + 72LL))(a1);
continue;
case 0xA9:
(*(*a1 + 80LL))(a1);
*(a1 + 8) -= 6LL;
continue;
case 0xAA:
(*(*a1 + 88LL))(a1);
continue;
case 0xAB:
(*(*a1 + 96LL))(a1);
*(a1 + 8) -= 4LL;
continue;
case 0xAC:
(*(*a1 + 104LL))(a1);
continue;
case 0xAD:
(*(*a1 + 112LL))(a1);
*(a1 + 8) += 2LL;
continue;
case 0xAE:
if ( *(a1 + 20) )
return 0LL;
*(a1 + 8) -= 12LL;
continue;
case 0xAF:
if ( *(a1 + 20) != 1 )
{
*(a1 + 8) -= 6LL;
continue;
}
return 1LL;
default:
puts("cmd execute error");
return 0LL;
}
}
}
实际上是一个switch+while循环，利用传入的参数进行寻址。我们通过动态调试来查看指令运行的先后顺序
在这里下个断点，输入32个1
发现这里的a1
有这么三个数，0xA8,0x10,0x40，再根据小端序，可得到一个地址为：0x4010A8
也正是我们所在的未知
然后这里的a3对应到了A9的地方，依次下去，发现执行的顺序是：
0xA9，0xA3，0xA5，0xA6，0xA4，0xAB，0xA7，0xAE，0xA2，0xAD，0xAF
我们把所有函数都翻译一下：
用python整理一下
opcode = [0xa9, 0xa3, 0xa5, 0xa6, 0xa4, 0xab, 0xa7, 0xae, 0xa2, 0xad, 0xaf]
for i in opcode:
if i == 0xa0:
print("r1++")
if i == 0xa1:
print("r2++")
if i == 0xa2:
print("r3++")
if i == 0xa3:
print("r1 -= r3")
if i == 0xa4:
print("r1 ^= r2")
if i == 0xa5:
print("r2 ^= r1")
if i == 0xa6:
print("r1 = 0xcd")
if i == 0xa7:
print("r2 = r1")
if i == 0xa8:
print("r3 = 0xcd")
if i == 0xa9:
print("r1 = input[r3]")
if i == 0xaa:
print("r2 = input[r3]")
if i == 0xab:
print("fun1()")
if i == 0xac:
print("func2()")
if i == 0xad:
print("func3()")
if i == 0xae:
print("if(r5==0)")
if i == 0xaf:
print("if(r5!=1)")
设输入数组为 input，r3 为索引 i，加密后的结果为 res[i]。
假设初始 r2 为 temp（初始值为 0）。
第一步：r1 = input[i]
第二步：r1 = input[i] - i
第三步：r2 = temp ^ (input[i] - i)
第四步：r1 = 0xcd
第五步：r1 = 0xcd ^ r2 = 0xcd ^ temp ^ (input[i] - i)
第六步：r2 = r1，即 r2 = 0xcd ^ temp ^ (input[i] - i)，此时 r2 就是加密后的结果 res[i]
那么反推到过来：已知 res[i] = 0xcd ^ temp ^ (input[i] - i)
对其进行变换可得：
input[i] = (temp ^ res[i] ^ 0xcd) + i
最终Exp:
res = [0xF4, 0x0A, 0xF7, 0x64, 0x99, 0x78, 0x9E, 0x7D, 0xEA, 0x7B, 0x9E, 0x7B, 0x9F, 0x7E, 0xEB, 0x71, 0xE8, 0x00, 0xE8, 0x07, 0x98, 0x19, 0xF4, 0x25, 0xF3, 0x21, 0xA4, 0x2F, 0xF4, 0x2F, 0xA6, 0x7C]
flag = ''
temp = 0
for i in range(0,32):
flag += chr((temp ^ res[i] ^ 0xcd) + i)
temp = res[i]
print(flag)
2.[HNCTF 2022 WEEK4]ez_maze
迷宫题，给的是用Py打包的exe
处理完之后的代码是：
# Visit https://www.lddgo.net/string/pyc-compile-decompile for more information
# Version : Python 3.9
map1 = [
[
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,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1],
[
1,
0,
1,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
0,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1],
[
1,
0,
1,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1,
0,
1],
[
1,
0,
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
0,
1],
[
1,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1],
[
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1],
[
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1,
0,
1],
[
1,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
1,
0,
1],
[
1,
0,
0,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1,
0,
1,
0,
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1],
[
1,
1,
1,
1,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1],
[
1,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1],
[
1,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1],
[
1,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1],
[
1,
0,
1,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1],
[
1,
0,
1,
0,
0,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1],
[
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
1,
0,
1,
1,
1,
0,
1],
[
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1],
[
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1,
0,
1,
0,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1],
[
1,
0,
0,
0,
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
1,
0,
1,
0,
1,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1],
[
1,
0,
1,
1,
1,
0,
1,
0,
1,
0,
1,
0,
1,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
1,
0,
1],
[
1,
0,
1,
0,
0,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1],
[
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1],
[
1,
0,
1,
0,
0,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1],
[
1,
0,
1,
1,
1,
0,
1,
0,
1,
0,
1,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1,
0,
1],
[
1,
0,
0,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
1,
0,
1,
0,
1,
0,
0,
0,
1,
0,
0,
0,
1,
0,
1,
0,
1],
[
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
0,
1],
[
1,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
1],
[
1,
0,
1,
1,
1,
1,
1,
0,
1,
1,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
0,
1],
[
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
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,
1,
1,
1,
1,
1,
1,
1,
1]]
path = str(input('please input your path:'))
x = 1
y = 1
for i in path:
if i not in 'wasd':
print('lose')
exit(0)
if i == 's':
y += 1
if i == 'w':
y -= 1
if i == 'a':
x -= 1
if i == 'd':
x += 1
if map1[y][x] != 0:
print('lose!')
exit(0)
if x == 29 and y == 29:
print('win!')
print('NSSCTF{md5(path)}')
continue
return None
这里我将地图打印出来
[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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]
[1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0]
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0]
[1, 0, 1, 0, 1, 0, 1, 0, 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, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1]
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0]
[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 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, 1, 1, 1, 1, 1, 1]
然后就是走迷宫了，肉眼不可走，上脚本
original_map = [
[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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 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, 1, 1, 1, 1, 1, 1, 1, 1]
]
# 转换地图为31x31
transformed_map = []
for row in original_map:
transformed_map.append(row[:-1])
transformed_map.append([1] * 31)
def dfs(maze, start, end, path=None):
if path is None:
path = []
path = path + [start]
if start == end:
return path
rows, cols = len(maze), len(maze[0])
x, y = start
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for dx, dy in directions:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < rows and 0 <= new_y < cols and maze[new_x][new_y] == 0 and (new_x, new_y) not in path:
new_path = dfs(maze, (new_x, new_y), end, path)
if new_path:
return new_path
return None
def path_to_wasd(path):
wasd_path = ""
for i in range(len(path) - 1):
current = path[i]
next_point = path[i + 1]
if next_point[0] > current[0]:
wasd_path += "s"
elif next_point[0] < current[0]:
wasd_path += "w"
elif next_point[1] > current[1]:
wasd_path += "d"
elif next_point[1] < current[1]:
wasd_path += "a"
return wasd_path
start = (1, 1)
end = (29, 29)
result = dfs(transformed_map, start, end)
if result:
wasd_result = path_to_wasd(result)
print("找到路径，用 wasd 表示:", wasd_result)
else:
print("未找到路径")
#ssssddssaassddddwwwwddwwddddddwwddddddssddwwddddddddssssaawwaassaassaassddssaassaawwwwwwaaaaaaaassaassddddwwddssddssssaassddssssaaaaaawwddwwaawwwwaassssssssssssddddssddssddddddddwwaaaaaawwwwddssddwwwwwwwwddssddss ssssssddddss
结束
3.