实在太菜了,前段时间刚刚做过迷宫问题,也做过N皇后问题。今天笔试做这个题,虽然明白是迷宫问题加个回溯就可以了,但愣是没做出来。太菜了,下来又花了点时间才做出来。
问题:一个(X,Y)的迷宫,入口左上角,出口右下角,求出走出迷宫的路径的条数。
# 算法:
def solution(map, row, col, x, y, count):if x <= row-1 and y <= col-1 and map[x][y] == 0:if x == row-1 and y == col-1:return 1else:return solution(map, row, col, x + 1, y, count) + solution(map, row, col, x, y + 1, count)else:return 0# 测试数据:
map = [[0, 0, 0, 0, 1],[1, 0, 0, 0, 1],[1, 0, 0, 0, 1],[1, 1, 0, 0, 1],[1, 1, 1, 0, 0]]k = solution(map, 5, 5, 0, 0, 0)
print(k)# 答案是 9
还得继续学习,一些算法题的拓展还需要学习,还要不断复习啊