首页 > 试题广场 >

精灵鼠从入口到出口的最少减少速度

[编程题]精灵鼠从入口到出口的最少减少速度

热度指数：3250 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

猛兽侠中精灵鼠在利剑飞船的追逐下逃到一个n*n的建筑群中，精灵鼠从（0,0）的位置进入建筑群，建筑群的出口位置为（n-1,n-1），建筑群的每个位置都有阻碍，每个位置上都会相当于给了精灵鼠一个固定值减速，因为精灵鼠正在逃命所以不能回头只能向前或者向下逃跑，现在问精灵鼠最少在减速多少的情况下逃出迷宫？

输入描述:

第一行迷宫的大小: n >=2 & n <= 10000；
第2到n+1行，每行输入为以','分割的该位置的减速,减速f >=1 & f < 10。

输出描述:

精灵鼠从入口到出口的最少减少速度？

示例1

输入

3
5,5,7
6,7,8
2,2,4

输出

算法知识视频讲解

Python

0b100001101000

n = int(input())
r = [list(map(int, input().split(','))) for _ in range(n)]

for i in range(n):
    for j in range(n):
        if i==0 and j>=1: r[i][j]+=r[i][j-1]
        elif j==0 and i>=1: r[i][j]+=r[i-1][j]
        elif i>=1 and j>=1: r[i][j]+=min(r[i-1][j],r[i][j-1])
print(r[n-1][n-1])

编辑于 2019-09-20 17:40:02 回复(1)