首页 > 试题广场 >

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

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

热度指数：3226 时间限制：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

输出

算法知识视频讲解

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)

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)