-
-
[原创]2021 KCTF 春季赛 南冥神功
-
发表于: 2021-5-13 13:45
-
这是一到迷宫题目，从S处出发，走过0路径，走过的0置为1，并最后到达出口。
查看代码，发现有8种移动方法
解题思路如下：
根据以上思路，编些代码如下：
import random
import copy
def mark(maze,pos):
maze[pos[0]][pos[1]] = 1
def remark(maze,pos):
maze[pos[0]][pos[1]] = 0
def passable(maze,pos):
status = maze[pos[0]][pos[1]] == 0
return status
# 这个递归函数的功能就是 走这一步，看看是否8个方向可以走，不可以走就返回false，回退到上一步，继续看其他方向def find_path(dirs,maze,pos,end):
mark(maze,pos) # pos位置已经走过
if pos == end:
correct_path.append(pos) # 到达了出口
return True
# 判断6个方向是否可以走动
for i in range(8):
nextpos = pos[0]+dirs[i][0],pos[1]+dirs[i][1] # 下一步，从左开始顺时针
if nextpos[0] < 0 or nextpos[1] < 0: # 不能走出界限
continue
if nextpos[0] > 8 or nextpos[1] > 9:
continue
if passable(maze,nextpos): # 该方向是否可以走动
find_path_status = find_path(dirs,maze,nextpos,end) # 这个方向可以走动,就走动到这个方向
if find_path_status:
correct_path.append(pos) # 这就说明下一层已经是出口路线
return True
else:
pass # 说明这个方向的下一步是死路，看看其他方向的下一步是否能走
remark(maze, pos)
return False # 8个方向不可以走动
def search_correct_path():
global correct_path
correct_sign = False # 正确标志位
dirsset = []
dirs = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1)]
originalmaze = [['S',0,1,0,0,1,0,0,1,1], \
[1,1,0,0,1,0,0,1,0,0], \
[0,0,1,0,1,1,1,1,1,0], \
[0,1,1,0,1,0,0,1,0,0], \
[0,0,1,0,0,1,0,0,1,1], \
[1,1,0,1,1,1,0,1,0,1], \
[0,0,1,1,1,1,0,1,0,1], \
[0,1,1,0,0,1,0,1,0,1], \
[0,0,0,1,0,0,1,1,0,0]]
maze = originalmaze
originalstart = (0, 0)
originalend = (8, 9)
status = True
while status:
for row in maze:
if 0 not in row:
correct_sign = True
else:
correct_sign = False
break
if correct_sign:
calculationop(list(reversed(correct_path)))
return
else:
correct_path = []
maze = copy.deepcopy(originalmaze)
while dirs in dirsset:
random.shuffle(dirs)
dirsset.append(copy.deepcopy(dirs))
status = find_path(dirs,maze, originalstart, originalend)
def calculationop(right_path):
op = []
for i in range(46):
raw = right_path[i][0]
con = right_path[i][1]
nexraw = right_path[i+1][0]
nexcon = right_path[i+1][1]
RAW = nexraw - raw
CON = nexcon - con
if CON==1 and RAW==0:
op.append(1)
elif raw%2==1 and CON==0 and RAW==1:
op.append(2)
elif raw%2==0 and CON==1 and RAW==1:
op.append(2)
elif raw%2==1 and CON==-1 and RAW==1:
op.append(3)
elif raw%2==0 and CON==0 and RAW==1:
op.append(3)
elif CON == -1 and RAW==0:
op.append(4)
elif raw%2==1 and CON ==-1 and RAW ==-1:
op.append(5)
elif raw%2==0 and CON==0 and RAW ==-1:
op.append(5)
elif raw%2==1 and CON==0 and RAW ==-1:
op.append(0)
elif raw%2==0 and CON==1 and RAW== -1:
op.append(0)
get_flag(op)
return
def get_flag(op):
flag = []
strspace = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def com(count, opfirst, opsecond):
for i in range(36):
first = 5 - (i + count) % 6
second = (count + i // 6) % 6
if first == opfirst and second == opsecond:
flag.append(strspace[i])
return
for count in range(23):
com(count, op[0], op[1])
for i in range(2):
op.pop(0)
print(''.join(flag))
return
if __name__ == '__main__':
correct_path = []
search_correct_path()
import random
import copy
def mark(maze,pos):
maze[pos[0]][pos[1]] = 1
def remark(maze,pos):
maze[pos[0]][pos[1]] = 0
def passable(maze,pos):
status = maze[pos[0]][pos[1]] == 0
return status
# 这个递归函数的功能就是 走这一步，看看是否8个方向可以走，不可以走就返回false，回退到上一步，继续看其他方向def find_path(dirs,maze,pos,end):
mark(maze,pos) # pos位置已经走过
if pos == end:
correct_path.append(pos) # 到达了出口
return True
# 判断6个方向是否可以走动
for i in range(8):
nextpos = pos[0]+dirs[i][0],pos[1]+dirs[i][1] # 下一步，从左开始顺时针
if nextpos[0] < 0 or nextpos[1] < 0: # 不能走出界限
continue
if nextpos[0] > 8 or nextpos[1] > 9:
continue
if passable(maze,nextpos): # 该方向是否可以走动
find_path_status = find_path(dirs,maze,nextpos,end) # 这个方向可以走动,就走动到这个方向
if find_path_status:
correct_path.append(pos) # 这就说明下一层已经是出口路线
return True
else:
pass # 说明这个方向的下一步是死路，看看其他方向的下一步是否能走
remark(maze, pos)
return False # 8个方向不可以走动
def search_correct_path():
global correct_path
correct_sign = False # 正确标志位
dirsset = []
dirs = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1)]
originalmaze = [['S',0,1,0,0,1,0,0,1,1], \
[1,1,0,0,1,0,0,1,0,0], \
[0,0,1,0,1,1,1,1,1,0], \
[0,1,1,0,1,0,0,1,0,0], \
[0,0,1,0,0,1,0,0,1,1], \
[1,1,0,1,1,1,0,1,0,1], \
[0,0,1,1,1,1,0,1,0,1], \
[0,1,1,0,0,1,0,1,0,1], \
[0,0,0,1,0,0,1,1,0,0]]
maze = originalmaze
originalstart = (0, 0)
originalend = (8, 9)
status = True
while status:
for row in maze:
if 0 not in row:
correct_sign = True
else:
correct_sign = False
break
if correct_sign:
calculationop(list(reversed(correct_path)))
return
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
最后于 2021-5-18 11:36
被kanxue编辑
，原因：
|
|
|---|---|
