Java题目训练——年终奖和迷宫问题
目录
一、年终奖
二、迷宫问题
一、年终奖
题目描述：
小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物， 每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设 计一个算法使小东拿到价值最高的礼物。 给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
题目解析：
本次利用动态规划的思想。
首先建立比棋盘多一行一列的状态数组（方便下标对应和状态初始化）。
其次找到状态方程，因为题目说他只能向下或者向右移动一步，所以当前状态arr[i][j] += 左上角的状态arr[i - 1][j - 1] + 左边和上边较大的那一方Math.max(arr[i - 1][j], arr[i][j - 1])。
再建立状态的初始化，由题目可知，左上角价值为0，所以arr[0][0] = 0。
由上，进行动态规划操作即可，更新状态数组，得到状态数组右下角的值即为能拿到的最大价值。
import java.util.Scanner;
public class Bonus {
public static int getMost(int[][] board){
int row = board.length;
int col = board[0].length;
//动态规划
//状态数组
int[][] arr = new int[row + 1][col + 1];
//初始化
arr[0][0] = 0;
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < col + 1; j++) {
arr[i][j] += board[i - 1][j - 1] + Math.max(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[row][col];
}
}二、迷宫问题
题目描述：
定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格 是可以走的路。
数据范围：2<=n,m<=10 ， 输入的内容只包含0<=val<=1
输入描述：
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只 有一条通道。
输出描述：
左上角到右下角的最短路径，格式如样例所示。
示例
示例1
输入：5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出：(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
说明：
示例2
输入：5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
输出：(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
说明：注意：不能斜着走！！
题目解析：
本题利用的思想是深度优先搜索（dfs），需要注意的是本题要求打印路径，所以我们可以利用一个二维顺序表存储路径，最后搜索完遍历打印结果即可。
详细讲解一下这里是如何进行深度优先算法的。
首先进行一些准备工作：
1. 建立状态数组flag，记录该位置走过没有。
2. 建立走迷宫的方向数组p = {{1, 0}, {0, 1}, {0, -1},{-1, 0}}，其中记录了按“右，下，左，上”的方向如何更新下一步。
然后就可以进行深度优先搜索了，需要注意的是，深度优先搜索是一种回溯思想，所以我们需要传入参数来标识此时的位置。
需要传入的参数有：迷宫数组maze，状态数组flag，迷宫的行数row和列数col（用来标识边界），此时位置的横坐标x和纵坐标y，记录路径的结果表ans。
进行搜索：
1. 查看是否超出迷宫边界。
2. 判断当前位置是否为通路，并且是之前没走过的。
(1). 如果是，将其加入结果表，看这个点是否为终点，如果是终点，返回true；如果不是，将此位置标记走过，寻找下一个点，判断下一个点是不是终点。
如果找完都没有返回true，说明此路不通，回退至上一步。
(2). 不是返回false。
搜索完毕后输出结果表即可。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int row = scanner.nextInt();
int col = scanner.nextInt();
int[][] maze = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
maze[i][j] = scanner.nextInt();
}
}
boolean[][] flag = new boolean[row][col];
List<List<Integer>> ans = new ArrayList<>();
dfs(maze, flag, row, col, 0, 0, ans);
for (int i = 0; i < ans.size(); i++) {
List<Integer> res = ans.get(i);
System.out.println("(" + res.get(0) + "," + res.get(1) + ")");
}
}
private static int[][] p = {{1, 0}, {0, 1}, {0, -1},{-1, 0}};
//深度优先搜索
public static boolean dfs(int[][] maze, boolean[][] flag, int row, int col, int x, int y, List<List<Integer>> ans){
//边界
if(x < 0 || x >= row || y < 0 || y >= col){
return false;
}
//位置没走过且是通路
if(maze[x][y] == 0 && !flag[x][y]){
List<Integer> res = new ArrayList<>();
res.add(x);
res.add(y);
ans.add(res);
//找到出口
if(x == row - 1 && y == col - 1){
return true;
}
//没找到出口，四个方向继续找
flag[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + p[i][0];
int newY = y + p[i][1];
if(dfs(maze, flag, row, col, newX, newY, ans)) {
return true;
}
}
//回退
flag[x][y] = false;
ans.remove(ans.size() - 1);
}
return false;
}
}如有建议或想法，欢迎一起讨论学习~