度小满 9.13 笔试情况（风控模型岗）
两道题：
1.迷宫花费最少时间
2.最大上升子序列的 方案
第一题：不知道从哪里终止条件，所以设了一个dfs的深度上限，好在AC了，有知道的告知一下
def dfs(x,y,cost,depth,max_depth):
if depth > max_depth:
return
cost += int(MAP[x][y])
if x==N-1 and y==N-1:
res.append(cost)
return
else:
if x-1>=0 and MAP[x-1][y] != '*':
dfs(x-1,y,cost,depth+1,max_depth)
if x+1<=N-1 and MAP[x+1][y] != '*':
dfs(x+1,y,cost,depth+1,max_depth)
if y-1>=0 and MAP[x][y-1] != '*':
dfs(x,y-1,cost,depth+1,max_depth)
if y+1<=N-1 and MAP[x][y+1] != '*':
dfs(x,y+1,cost,depth+1,max_depth)
return
if __name__ == '__main__':
N,K = list(map(int,input().split()))
MAP = []
for i in range(N):
line = input()
line = line.replace('1','*').replace('0','1').replace('#',str(K))
MAP.append([c for c in line])
res = []
dfs(0,0,0,0,4*N)
if res == []:
print('No solution')
else:
print(min(res)-1) 
