题目考察了迷宫寻路(探索)机制，注册码验证算法逆向实现如下：
#注册码检查算法，4B3CFB
def checkSeri(seri, map):
sbox = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
iCol = 0
iRow = 0
iSeri = -1
for chr in seri:
iSbox = sbox.find(chr)
iSeri += 1
op1 = 5 - (iSeri + iSbox) % 6
op2 = (iSeri + iSbox // 6) % 6
successed = False
for op in [op1, op2]:
if op == 1:
iCol += 1
elif op == 2:
if iRow & 1 == 0:
iCol += 1
iRow += 1
elif op == 3:
if iRow & 1 != 0:
iCol -= 1
iRow += 1
elif op == 4:
iCol -= 1
elif op == 5:
if iRow & 1 != 0:
iCol -= 1
iRow -= 1
else:
if iRow & 1 == 0:
iCol += 1
iRow -= 1
print("(" + str(iRow) + ", " + str(iCol) + ", " + str(op) + "), ")
if iCol > 9 or iRow > 8 or iCol < 0 or iRow < 0 or map[iRow][iCol] != 0:
break
map[iRow][iCol] = 1
continue
successed = True
for line in map:
for v in line:
if v == 0:
successed = False
break
if successed == False:
break
if successed == False:
print("failed:" + seri)
else:
print("successed:" + seri)
return successed此迷宫可向8个方向探索，已经探索过的区域不可重复探索，结束条件为探索完成所有未知区域，如果将迷宫地图视作二维数组，那么在寻路过程中需要满足特定的规则：
偶数行不可向左上及左下寻路
奇数行不可向右上及右下寻路
迷宫地图定义如下：
# 地图中‘非0位置’被视为障碍物，不可寻路，‘0位置’被视为需要探索的未知区域
g_map = [
[0x53, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, ], #0
[0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, ],
[0x00, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, ], #2
[0x00, 0x01, 0x01, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, ],
[0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, ], #4
[0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x01, ],
[0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x01, ], #6
[0x00, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, ],
[0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, 0x00, 0x00, ], #8
]
编写探索寻路算法如下：
def __copyMap(map):
newMap = []
for line in map:
newLine = line[:]
newMap.append(newLine)
return newMap
def __checkRowLimit(row):
return row >= 0 and row <= 8
def __checkColLimit(col):
return col >= 0 and col <= 9
def __checkPositionValid(row, col, table):
return __checkRowLimit(row) and __checkColLimit(col) and table[row][col] == 0
def __isFinished(table):
for line in table:
for v in line:
if v == 0:
return False
return True
#寻路算法， 从（row, col）开始
def searchPath(row, col, map):
path = []
map[row][col] = 1
if __isFinished(map):
return True, path
choices = []
if row & 1 == 0 :
#偶数行
if __checkPositionValid(row, col - 1, map):
choices.append((row, col - 1, 4)) #左
if __checkPositionValid(row - 1, col, map):
choices.append((row - 1, col, 5)) #上
if __checkPositionValid(row - 1, col + 1, map):
choices.append((row - 1, col + 1, 0)) #右上
if __checkPositionValid(row, col + 1, map):
choices.append((row, col + 1, 1)) #右
if __checkPositionValid(row + 1, col + 1, map):
choices.append((row + 1, col + 1, 2)) #右下
if __checkPositionValid(row + 1, col, map):
choices.append((row + 1, col, 3)) #下
else:
#奇数行
if __checkPositionValid(row, col - 1, map):
choices.append((row, col - 1, 4)) #左
if __checkPositionValid(row - 1, col - 1, map):
choices.append((row - 1, col - 1, 5)) #左上
if __checkPositionValid(row - 1, col, map):
choices.append((row - 1, col, 0)) #上
if __checkPositionValid(row, col + 1, map):
choices.append((row, col + 1, 1)) #右
if __checkPositionValid(row + 1, col, map):
choices.append((row + 1, col, 2)) #下
if __checkPositionValid(row + 1, col - 1, map):
choices.append((row + 1, col - 1, 3)) #左下
#若无路可走，则返回失败
if len(choices) == 0:
return False, []
#遍历寻路
for choice in choices:
finished, nexts = searchPath(choice[0], choice[1], __copyMap(map))
#若此路不通，更换路线
if finished == False:
continue
#寻路正确，返回路径
row = choice[0]
col = choice[1]
path.append((row, col, choice[2]))
for elem in nexts:
path.append(elem)
return True, path
#所有路线皆不可通， 则返回失败
return False, []
注册码生成算法如下：
#计算对应op的注册码字符
def calcSeriCharByOps(iSeri, op1, op2):
cbox = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
iCol = 0
iRow = 0
for iCbox in range(0, len(cbox)):
_op1 = 5 - (iSeri + iCbox) % 6
_op2 = (iSeri + iCbox // 6) % 6
if (op1 == _op1 and op2 == _op2):
return cbox[iCbox]
return ''
finished, path = searchPath(0, 0, __copyMap(g_map))
if finished == False:
print("寻路失败")
else:
# strPath = ""
# for node in path:
# strPath += "(" + str(node[0]) + ", " + str(node[1]) + ", " + str(node[2]) + "), "
# print(strPath)
seri = ""
iSeri = 0
for i in range(0, len(path) // 2):
seri += calcSeriCharByOps(iSeri, path[i * 2][2], path[i * 2 + 1][2])
iSeri += 1
#checkSeri(seri, g_map)
print("注册码：" + seri) #注册码：GJ0V4LA4VKEVQZSVCNGJ00N
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
