蓝桥杯|2021模拟赛跳跃 java_dfs_动态规划蓝桥杯|dfs|java

【蓝桥杯|2021模拟赛跳跃 java_dfs_动态规划】
文章图片

文章图片

分析

我们可以发现，从一个点开始，一共有9个点可以到达，我们通过dfs，用一个for循环搜索这9个可达点；
在搜索时，对于多个方向走的问题，我们用一个偏移量dx_dy，一维为x,二维为y；我们要注意判断对当前点x,y加上偏移量后变成的xx,yy要判断其是否在有效范围内，不能越界；
dfs出口就是，搜索到了终点，我们用一个ans来记录到达终点的最大权值和；通过取当前的ans值和该条路径权值和的最大值；

import java.util.Scanner; public class Main { static int n, m; static int[][] map = new int[105][105]; //每个点的权值 static int[][] vis = new int[105][105]; //标记访问情况 static int[][] dx_dy = {{0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 2}, {1, 3}, {2, 0}, {2, 2}, {3, 0}}; //可到达的点，共9个 static int ans = Integer.MIN_VALUE; static void dfs(int x, int y, int sum) {//sum:到当前(x,y)点的权值和 if (x == n - 1 && y == m - 1) { //搜索到终点 ans = Math.max(ans, sum); //判断此条路径，是否比上一条更优 return; } for (int i = 0; i < 9; i++) {//从当前点到可已到达的9点，都要搜索一波 int xx = x + dx_dy[i][0]; int yy = y + dx_dy[i][1]; if (vis[xx][yy] == 0 && xx >= 0 && yy >= 0 && xx < n && yy < m) {//多个方向走的问题，不能越界 vis[xx][yy] = 1; dfs(xx, yy, sum + map[xx][yy]); vis[xx][yy] = 0; } } }public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { map[i][j] = scanner.nextInt(); } } dfs(0, 0, map[0][0]); //从起点出发 System.out.println(ans); } }