华为笔试题2019年4月10日第三题（地图海拔路径数量）

# -*- 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=4
M=5
height=[[0,1,0,0,0],[0,2,3,0,0],[0,0,4,5,0],[0,0,7,6,0]]
start_i=0
start_j=1
target_i=3
target_j=2total_count=0#总路径数
visited=[[0 for i in range(0,M)] for j in range(0,N)]#访问过的点置1
def dps(cur_i,cur_j,target_i,target_j,visited,height):visited[cur_i][cur_j]=1if cur_i==target_i and cur_j==target_j:global total_counttotal_count+=1returnif 0<=cur_j-1height[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]=0if 0<=cur_i-1height[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]=0if 0<=cur_j+1height[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]=0if 0<=cur_i+1height[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]=0returndps(start_i,start_j,target_i,target_j,visited,height)
print(total_count)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！