度小满 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)