Java题目训练——年终奖和迷宫问题

痛定思痛。 2023-09-30 21:59 10阅读 0赞

**目录**

一、年终奖

二、迷宫问题

--------------------

### 一、年终奖 ###

题目描述：

> 小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个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;
        }
    }

如有建议或想法，欢迎一起讨论学习~