首页 > 试题广场 >

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

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

热度指数：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

输出

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
    "bufio"
    "os"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var n int
    fmt.Scan(&n)
    mat:=make([][]int,n)
    for i,_:=range mat{
        mat[i]=[]int{}
        s,_:=in.ReadString('\n')
        for _,ch:=range s{
            if ch>='0'&&ch<='9'{
                mat[i]=append(mat[i],int(ch-'0'))
            }
        }
    }
    for i:=1;i<n;i++{
        mat[i][0]+=mat[i-1][0]
        mat[0][i]+=mat[0][i-1]
    }
    for i:=1;i<n;i++{
        for j:=1;j<n;j++{
            mat[i][j]+=min(mat[i-1][j],mat[i][j-1])
        }
    }
    fmt.Print(mat[n-1][n-1])
}

func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}

发表于 2023-03-21 10:41:18 回复(0)