首页 > 试题广场 >

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

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

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

输出

算法知识视频讲解

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s;
    vector<vector<int>>num(n,vector<int>(n)),dp(n,vector<int>(n,0));
    for(int i=0;i<n;i++)
    {
        cin>>s;
        int t=0;
        for(int j=0;j<n;j++,t+=2)
            num[i][j]=s[t]-'0';
    }
    dp[0][0]=num[0][0];
    for(int i=1;i<n;i++)
        dp[i][0]=num[i][0]+dp[i-1][0];
    for(int j=1;j<n;j++)
        dp[0][j]=dp[0][j-1]+num[0][j];
    for(int i=1;i<n;i++)
        for(int j=1;j<n;j++)
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+num[i][j];
    cout<<dp[n-1][n-1]<<endl;
    return 0;
}

发表于 2019-08-13 19:32:23 回复(2)

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

int main(const int argc, const char* const argv[]) {
  int n;
  fscanf(stdin, "%d\n", &n);
  
  int x, y, grid[n][n];
  for (y = 0; y < n; ++y)
    for (x = 0; x < n; ++x)
      fscanf(stdin, "%d,", *(grid + y) + x);
  
  for (x = 1; x < n; ++x) grid[0][x] += grid[0][x - 1];
  for (y = 1; y < n; ++y) grid[y][0] += grid[y - 1][0];
  
  for (y = 1; y < n; ++y)
    for (x = 1; x < n; ++x)
      grid[y][x] += fmin(grid[y - 1][x], grid[y][x - 1]);
  
  fprintf(stdout, "%d\n", grid[n - 1][n - 1]);
  return 0;
}

发表于 2021-08-05 19:09:25 回复(0)

pein531

一道非常典型的动态规划题

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null){
            int n = Integer.parseInt(strN);
            int[][] matrix = new int[n][n];
            for(int i = 0; i < n; i++){
                String[] strRow = br.readLine().trim().split(",");
                for(int j = 0; j < n; j++){
                    matrix[i][j] = Integer.parseInt(strRow[j]);
                }
            }
            System.out.println(solve(matrix, n));
        }
    }
    
    // 动态规划求解最小路径
    private static int solve(int[][] dp, int n) {
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 && j == 0)
                    continue;
                else if(i == 0)
                    dp[i][j] += dp[i][j - 1];
                else if(j == 0)
                    dp[i][j] += dp[i - 1][j];
                else
                    dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n - 1][n - 1];
    }
}

发表于 2020-10-26 11:27:44 回复(0)

Java

lmz9509

/*
递归的思想：试一试(不太行，超时了)
*//*
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        for(int i = 0;i<n;i++){
            String[] str = br.readLine().split(",");
            for(int j = 0;j<n;j++){
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        int count = Fuc(0,0,n,arr);
        System.out.println(count);
    }
    
    //
    public static int Fuc(int x,int y,int n,int[][] arr){
        if(x==n-1 && y==n-1)return arr[x][y];
        if(x == n-1 && y<n-1)return Fuc(x,y+1,n,arr)+arr[x][y];
        if(x < n-1 && y == n-1)return Fuc(x+1,y,n,arr)+arr[x][y];
        return Math.min(Fuc(x+1,y,n,arr),Fuc(x,y+1,n,arr))+arr[x][y];//两者选最小
    }
}*/


/*
动态规划试一试：dp[i][j]:表示到达坐标[i,j]时产生的最少减速
状态转移：
dp[i][j] = Min(dp[i-1][j],dp[i][j-1]) + arr[i][j];
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        for(int i = 0;i<n;i++){
            String[] str = br.readLine().split(",");
            for(int j = 0;j<n;j++){
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        int[][] dp = new int[n][n];
        dp[0][0] = arr[0][0];//dp[0][1] = dp[0][0]+arr[0][1];
        //dp[1][0] = dp[0][0] + arr[1][0];
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                if(i==0 &&j==0)continue;
                //边界情况，i==0时dp[0][j]=dp[0][j-1]+arr[0][j];
                if(i==0){
                    dp[0][j]=dp[0][j-1]+arr[0][j];
                    continue;
                }
                //边界情况，j==0时dp[i][0]=dp[i-1][0]+arr[i][0];
                if(j==0){
                    dp[i][0]=dp[i-1][0]+arr[i][0];
                    continue;
                }
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + arr[i][j];
            }
        }
        System.out.println(dp[n-1][n-1]);
    }
}

发表于 2020-05-23 15:12:43 回复(0)

Java

LHC0512

Java解法动态规划

import java.util.Scanner;

public class Main {
    /**
     * 运行时间：544ms
     *
     * 占用内存：86024k
     * */
    public static void main(String[] args) {
        //取输入的数据
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        int[][] num = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] s = scanner.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                num[i][j]=Integer.parseInt(s[j]);
            }
        }
        
        int[][] dp= new int [n][n];
        dp[0][0]=num[0][0];
        for(int i=1;i<n;i++){
            dp[i][0]=num[i][0]+dp[i-1][0];
            dp[0][i]=num[0][i]+dp[0][i-1];
        }

        for(int i=1;i<n;i++)
            for(int j=1;j<n;j++)
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+num[i][j];
        System.out.println(dp[n-1][n-1]);
    }
}

发表于 2020-03-01 19:51:47 回复(0)

EnvyEvil

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

for i in range(1, n):
    f_matrix[i][0] += f_matrix[i - 1][0]
    f_matrix[0][i] += f_matrix[0][i - 1]

for i in range(1, n):
    for j in range(1, n):
        f_matrix[i][j] += min(f_matrix[i - 1][j], f_matrix[i][j - 1])
print(f_matrix[-1][-1])

发表于 2019-10-06 20:40:59 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n][n], dp[n][n];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<n;j++)
            a[i][j] = s[j<<1]-'0';
    }

    dp[0][0] = a[0][0];
    for(int i=1;i<n;i++)
        dp[i][0] = dp[i-1][0] + a[i][0];
    for(int i=1;i<n;i++)
        dp[0][i] = dp[0][i-1] + a[0][i];
    for(int i=1;i<n;i++)
        for(int j=1;j<n;j++)
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j];
    cout<<dp[n-1][n-1]<<endl;
    return 0;
}

发表于 2019-10-04 01:55:29 回复(0)

C/C++

昔遥暮云

#include <bits/stdc++.h>
//格式化输入+动态规划+空间压缩
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> dp(n,0);
    scanf("%d",&dp[0]);    
    for(int j=1;j<n;j++){    //初始化第一行
        scanf(",%d",&dp[j]);
        dp[j]+=dp[j-1];
    }
    for(int i=1;i<n;i++){    //从上往下，从左往右最小累加
        int pre=dp[0];
        scanf("%d",&dp[0]);
        dp[0]+=pre;
        for(int j=1;j<n;j++){
            int up=dp[j];
            scanf(",%d",&dp[j]);
            dp[j]+=min(up,dp[j-1]);
        }
    }
    cout<<dp[n-1];
    return 0;
}

发表于 2019-09-18 10:18:14 回复(0)

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)

Java

谁的电脑

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] str = br.readLine().split(",");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(str[j]);
            }
        }
        int[][] dp = new int[n][n];
        dp[0][0] = map[0][0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + map[0][i];
        }
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + map[i][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + map[i][j];
            }
        }
        System.out.println(dp[n - 1][n - 1]);
    }
}

编辑于 2019-08-20 16:07:44 回复(0)

小谷围做题家

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)

连三月s

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] map = new int[n + 1][n + 1];
        String[] tmp = null;
        sc.nextLine();
        //System.out.println(sc.nextLine());
        
        int[][] f = new int[n + 1][n + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE);

        for (int i = 1; i <= n; i++) {
            tmp = sc.nextLine().split(",");
            Arrays.fill(f[i], Integer.MAX_VALUE);
            
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(tmp[j - 1]);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 && j == 1) f[i][j] = map[i][j];
                else f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + map[i][j];
            }
        }
        System.out.println(f[n][n]);
        
        
    }
}

发表于 2022-03-04 19:41:50 回复(0)

我去2000年啦

n=eval(input("输入矩阵大小n=: "))
res=[]
for j in range(n):
    r=[]
    for i in range(n):
        r.append(eval(input("输入矩阵元素，以逗号隔开: ")))
    res.append(r)
ans=[[0 for _ in range(n)] for _ in range(n)]
ans[0][0]=res[0][0]
for l in range(1,n):
    ans[l][0] = res[l][0] + ans[l-1][0]
    ans[0][l] = res[0][l] + ans[0][l-1]
for k in range(1,n):
    for m in range(1,n):
        ans[k][m]=res[k][m]+min(ans[k-1][m],ans[k][m-1])
print(ans[n-1][n-1])

发表于 2020-12-01 19:29:34 回复(0)

dong412

python 动态规划

import sys
line=sys.stdin.readline().strip()
n=int(line)
def func(n):
    num=[]
    for _ in range(n):
        l=sys.stdin.readline().strip()
        lin=l.split(',')
        a=list(map(int,lin))
        num.append(a)
    m=len(num[0])
    dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
    dp[1][1]=num[0][0]
    for i in range(n):
        for j in range(m):
            if i==0:
                dp[i+1][j+1]=num[i][j]+dp[i+1][j]
            elif j==0:
                dp[i+1][j+1]=num[i][j]+dp[i][j+1]
            else:
                dp[i+1][j+1]=min(dp[i+1][j]+num[i][j],dp[i][j+1]+num[i][j])
 
    return dp[n][m]
 
res=func(n)
print(res)

发表于 2020-08-12 22:29:50 回复(0)

lhyAira

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[][] arr = new int[n][];
            for (int i = 0; i < n; i++)
            {
                arr[i] = Console.ReadLine().Split(',').Select(x => int.Parse(x)).ToArray();
            }

            int[][] dp = new int[n][];
            for (int r = 0; r < n; r++)
            {
                dp[r] = new int[n];
            }

            dp[0][0] = arr[0][0];
            for (int r = 0; r < n; r++)
            {
                for (int c = 0; c < n; c++)
                {
                    if (r - 1 < 0 && c - 1 < 0)
                    {
                        continue;
                    }
                    else if (r - 1 < 0)
                    {
                        dp[r][c] = arr[r][c] + dp[r][c - 1];
                    }
                    else if (c - 1 < 0)
                    {
                        dp[r][c] = arr[r][c] + dp[r - 1][c];
                    }
                    else
                    {
                        dp[r][c] = arr[r][c] + Math.Min(dp[r - 1][c], dp[r][c - 1]);
                    }
                }
            }

            Console.WriteLine(dp[n - 1][n - 1]);
            Console.ReadLine();
        }

发表于 2020-05-28 14:05:03 回复(0)

局外人20190909161897

import sys
class Solution:
    def minpath():
        n=int(sys.stdin.readline().strip())
        num=[]
        for i in range(n):
            line=[int(i) for i in sys.stdin.readline().strip().split(',')]
            num.append(line)
        #print(num)
        #print(num[0][0])
        inf = 1000000
        d=[[0]*n]*n
        #d[0][0]=num[0][0]
        print(d[0][0])
        for i in range(n):
            for j in range(n):
                if j==0:
                    d[i][j]=d[i-1][j]+num[i-1][j]
                elif i ==0:
                    d[i][j]=d[i][j-1]+num[i][j-1]
                else:
                    if d[i-1][j]<d[i][j-1]:
                        d[i][j]=d[i-1][j]+num[i][j]
                    else:
                        d[i][j]=d[i][j-1]+num[i][j]
        print(d[n-1][n-1])
if __name__=='__main__':
    Solution.minpath()

发表于 2019-09-10 12:38:40 回复(0)

hzdms

n = int(input())
matrix = []
for i in range(n):
    matrix.append(list(map(int, input().split(","))))

for i in range(1, n):
    matrix[0][i] = matrix[0][i - 1] + matrix[0][i]
    matrix[i][0] = matrix[i - 1][0] + matrix[i][0]
for i in range(1, n):
    for j in range(1, n):
        matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1]) +  matrix[i][j]
print(matrix[-1][-1])

发表于 2019-09-04 06:05:01 回复(0)

闷死作大死

/**
 * 精灵鼠, 动态规划
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = Integer.valueOf(scanner.nextLine());
        int[][] maze = new int[num][num];

        for (int i = 0; i < num; i++) {
            String[] line = scanner.nextLine().split(",");
            for (int j = 0; j < num; j++) {
                maze[i][j] = Integer.valueOf(line[j]);
            }
        }

        // 消耗满足: f(maze[m][n]) = min(f(maze[m-1][n]), f(maze[m][n-1])) + maze[m][n]
        for (int m = 0; m < num; m++) {
            for (int n = 0; n < num; n++) {
                boolean mFlag = m == 0, nFlag = n == 0;
                if (mFlag && nFlag) {
                    // do nothing
                } else if (mFlag) {
                    maze[m][n] += maze[m][n-1];
                } else if (nFlag) {
                    maze[m][n] += maze[m-1][n];
                } else {
                    maze[m][n] += Math.min(maze[m - 1][n], maze[m][n - 1]);
                }
            }
        }

        System.out.println(maze[num-1][num-1]);
    }
}

发表于 2019-08-20 10:46:24 回复(0)

肖201904252113170

"""
最短消耗路径
思路：
1. 数据预处理，n，价值矩阵
2. 动态规划
"""
class Solution():
    def shortedMatrix(self):
        while True:
            try:
                n = int(input())  #迷宫的大小 n*n
                matrix = []   #路径消耗矩阵
                for i in range(n):
                    matrix.append(list(map(int, input().split(','))))
                #DP
                dp = [[0]*n for _ in range(n)]   #dp[n][n]全部初始化为0
                for i in range(n):
                    for j in range(n):
                        if i==0 and j == 0:  #初始化最开始的[0][0]处的结果
                            dp[i][j] = matrix[i][j]
                        elif i == 0:
                            #第一列的结果,只能向下走
                            dp[i][j] = matrix[i][j] + dp[i][j-1]
                        elif j == 0:
                            #第一行，只能向前走
                            dp[i][j] = matrix[i][j] + dp[i-1][j]
                        else:
                            #中间位置，可以向前、下走，取最小值
                            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
                print(dp[-1][-1])
            except:
                break
if __name__ == '__main__':
     Solution().shortedMatrix()

发表于 2019-08-19 15:00:57 回复(0)

●201904162303344

import java.util.*;
import java.math.*;
public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        while(s.hasNext())
        {
            int n=s.nextInt();
            int num[][]=new int[n][n];
            String st[]=new String[n];

            s.nextLine();

            for(int i=0;i<n;i++)
                st[i]=s.nextLine();

            for(int i=0;i<n;i++)
            {
                String stx[]=st[i].split(",");
                for(int j=0;j<n;j++)
                {
                    num[i][j]=Integer.valueOf(stx[j]);
                }
            }

            for(int i=n-2;i>=0;i--)
            {
                num[n-1][i]+=num[n-1][i+1];
                num[i][n-1]+=num[i+1][n-1];
            }

            for(int i=n-2;i>=0;i--)
            {
                for(int j=i;j>=0;j--)
                {
                    num[i][j]+=Math.min(num[i+1][j],num[i][j+1]);
                    if(i!=j)
                    {
                        num[j][i]+=Math.min(num[j+1][i],num[j][i+1]);
                    }
                }
            }
            System.out.println(num[0][0]);
        }
    }
}

发表于 2019-08-15 10:50:55 回复(0)