# -*- coding: utf-8 -*-"""Created on Thu Apr 11 09:02:20 2019@author: CommissarMa华为笔试题2019年4月10日第三题题目：一张N*M的地图上每个点的海拔高度不同；从当前点只能访问上、下、左、右四个点中还没有到达过的点，且下一步选择的点的海拔高度必须高于当前点；求从地图中的点A到点B总的路径条数除以10^9的余数。地图上左上角坐标为(0,0),右下角坐标为(N-1,M-1)。""""""深度优先遍历DPS"""#输入：N=4M=5height=[ [0,1,0,0,0], [0,2,3,0,0], [0,0,4,5,0], [0,0,7,6,0] ]start_i=0start_j=1target_i=3target_j=2total_count=0#总路径数visited=[[0 for i in range(0,M)] for j in range(0,N)]#访问过的点置1def dps(cur_i,cur_j,target_i,target_j,visited,height): visited[cur_i][cur_j]=1 if cur_i==target_i and cur_j==target_j: global total_count total_count+=1 return if 0<=cur_j-1<M and height[cur_i][cur_j-1]>height[cur_i][cur_j] and visited[cur_i][cur_j-1]==0: dps(cur_i,cur_j-1,target_i,target_j,visited,height)#左边 visited[cur_i][cur_j-1]=0 if 0<=cur_i-1<N and height[cur_i-1][cur_j]>height[cur_i][cur_j] and visited[cur_i-1][cur_j]==0: dps(cur_i-1,cur_j,target_i,target_j,visited,height)#上边 visited[cur_i-1][cur_j]=0 if 0<=cur_j+1<M and height[cur_i][cur_j+1]>height[cur_i][cur_j] and visited[cur_i][cur_j+1]==0: dps(cur_i,cur_j+1,target_i,target_j,visited,height)#右边 visited[cur_i][cur_j+1]=0 if 0<=cur_i+1<N and height[cur_i+1][cur_j]>height[cur_i][cur_j] and visited[cur_i+1][cur_j]==0: dps(cur_i+1,cur_j,target_i,target_j,visited,height)#下边 visited[cur_i+1][cur_j]=0 returndps(start_i,start_j,target_i,target_j,visited,height)print(total_count)