首页 > 编程语言 >java:跳跃——寻找路径

java:跳跃——寻找路径

时间:2023-01-08 19:24:06浏览次数:42  
标签:java Scanner scan int 行第 路径 && 跳跃 dp

题目描述

小蓝在一个n行m列的方格图中玩一个游戏。

开始时,小蓝站在方格图的左上角,即第1行第1列。

小蓝可以在方格图上走动,走动时,如果当前在第r 行第 c 列,他不能走到行号比 r 小的行,也不能走到列号比 c 小的列。同时,他一步走的直线距离不超过 3。

  例如,如果当前小蓝在第 33 行第 55 列,他下一步可以走到第 3 行第 6 列、第 3 行第 7 列、第 3 行第 8 列、第 4 行第 5 列、第 4 行第 6 列、第 4 行第 7 列、第 5 行第 5 列、第 5 行第 6 列、第 6 行第 5 列之一。

小蓝最终要走到第 n 行第 m 列。

在图中,有的位置有奖励,走上去即可获得,有的位置有惩罚,走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值,奖励为正,惩罚为负。

小蓝希望,从第 1 行第 1 列走到第 n 行第 m 列后,总的权值和最大。请问最大是多少?

输入描述

输入的第一行包含两个整数 n, mn,m,表示图的大小。

接下来 nn 行,每行 mm 个整数,表示方格图中每个点的权值。

其中, 10^4≤n≤100,−10^4≤权值≤10^4。

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a=scan.nextInt();
        int b=scan.nextInt();
        int[][] arr=new int[a][b];
        for(int i=0;i<a;i++){
          for(int j=0;j<b;j++){
            arr[i][j]=scan.nextInt();
          }
        }
        //路径寻找 ———— 通过二维数组进行路径权值的填充
        int[][] dp=new int[a][b];
        for(int i=0;i<a;i++){
          for(int j=0;j<b;j++){
            dp[i][j]=-1000000; //设置起始最小值 —— 小于-10^4
            for(int k=i;k>=0 && i-k<=3;k--){  // k>=0 二维数组范围 i-k<=3 只能挑动三格
              for(int l=j;l>=0 && (i-k-l+j<=3);l--){
                dp[i][j]=Math.max(dp[i][j],dp[k][l]+arr[i][j]);
              }
            }
            if(i==0&&j==0) dp[i][j]=arr[i][j];
          }
        }
      System.out.println(dp[a-1][b-1]);
    }
}

 

import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main {     public static void main(String[] args) {         Scanner scan = new Scanner(System.in);         int a=scan.nextInt();         int b=scan.nextInt();         int[][] arr=new int[a][b];         for(int i=0;i<a;i++){           for(int j=0;j<b;j++){             arr[i][j]=scan.nextInt();           }         }         //路径寻找 ———— 通过二维数组进行路径权值的填充         int[][] dp=new int[a][b];         for(int i=0;i<a;i++){           for(int j=0;j<b;j++){             dp[i][j]=-1000000; //设置起始最小值 —— 小于-10^4             for(int k=i;k>=0 && i-k<=3;k--){  // k>=0 二维数组范围 i-k<=3 只能挑动三格               for(int l=j;l>=0 && (i-k-l+j<=3);l--){                 dp[i][j]=Math.max(dp[i][j],dp[k][l]+arr[i][j]);               }             }             if(i==0&&j==0) dp[i][j]=arr[i][j];           }         }       System.out.println(dp[a-1][b-1]);     } }

标签:java,Scanner,scan,int,行第,路径,&&,跳跃,dp
From: https://www.cnblogs.com/mcpf/p/17035137.html

相关文章

  • JAVA 内部类
    内部类内部类就是在一个类的内部再定义一个类,比如A类中定义了一个B类,那么B类相对A类来说就称为内部类,而A类相对与B类来说就是外部类了。成员内部类静态内部类局部内部......
  • Java面试题笔记
    1Hystrix的状态有哪些closed->open:正常情况下熔断器为closed状态,当访问同一个接口次数超过设定阈值并且错误比例超过设置错误阈值的时候,就会打开熔断机制,这时候熔断......
  • JAVA 接口
    普通类:只有具体实现抽象类:具体实现和规范(抽象方法)都有!接口:只有规范!自己无法写方法~专业约束~约束和实现分离:面向接口编程~  接口就是规范,定义的是一组规则,体现了......
  • JavaWeb概述
    笔记目录:(https://www.cnblogs.com/wenjie2000/p/16378441.html)参考视频:黑马程序员新版JavaWeb基础教程,Javaweb从入门到企业实战完整版注意:javaWeb部分包含了前端和后......
  • 【Java】四种引用和引用队列的概念
    四种引用类型强引用(StrongReference)强引用就是指在程序代码之中普遍存在的,比如下面这段代码中的object和str都是强引用:Objectobject=newObject();Stringstr=......
  • javascript 操作剪切板
    此库优点:支持电脑和手机端浏览器第一步:声明一个对象$(function(){varclipboard=newClipboardJS(document.getElementById("btnCopyFileShareLink"......
  • JAVA工程师学习教程之Set和HashMap集锦
    day14_JAVAOOP课程目标1.【理解】Set集合的特点2.【理解】Set集合不重复的原理3.【掌握】HaseSet集合的基本使用4.【理解】LinkedHashSet的特点5.【理解】Map集......
  • JAVAEE工程师零基础学习教程之泛型类和File类
    day15_JAVAOOP课程目标1.【理解】什么是泛型2.【掌握】泛型的基本使用3.【理解】什么是Collections工具类4.【理解】什么是File类5.【掌握】File类的常用功能6.......
  • java并发编程_线程
    创建进程方式1,start一个新的线程,启动线程后回调newRunnable中的run方法,run方法调用结束后,JVM等待回收线程。publicclassFutureTaskOne{publicstaticvoidmai......
  • Java中Elasticsearch 实现分页方式(三种方式)
    目录ES简介ES的特点:一、from+size浅分页二、scroll深分页scroll删除三、search_after深分页ES简介Elasticsearch是一个基于Lucene实现的......