刷题_24：年终奖 and 迷宫问题

Myth丶恋晨 2023-09-30 21:46 62阅读 0赞

### 一.年终奖 ###

**题目链接：**

> [年终奖][Link 1]

**题目描述：**

> **小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。  
> 给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为\[0,0\],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。**

**输入描述：**

> **无**

**输出描述：**

> **无**

**示例1：**

> **无**

**个人总结：**

> **动态规划题目，和之前写过的题目一模一样 [走方格数][Link 2]**

**代码实现：**

import java.util.*;
    
    public class Bonus {
        
        public int getMost(int[][] board) {
        
            // write code here
            int row = board.length;
            int col = board[0].length;
            int[][] dp = new int[row][col];
            for (int i = 0; i < row; i++) {
        
                for (int j = 0; j < col; j++) {
        
                    if (i == 0 && j == 0) {
        
                        dp[i][j] = board[i][j];
                    } else if (i == 0) {
        
                        dp[i][j] += dp[i][j - 1] + board[i][j];
                    } else if (j == 0) {
        
                        dp[i][j] += dp[i - 1][j] + board[i][j];
                    } else {
        
                        dp[i][j] += Math.max(dp[i - 1][j], dp[i][j - 1]) + board[i][j];
                    }
                }
            }
            return dp[row - 1][col - 1];
        }
    }

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

### 二.迷宫问题 ###

**题目链接：**

> [迷宫问题][Link 3]

**题目描述：**

> **定义一个二维数组 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)**

**个人总结：**

> **深度优先搜索题，一切尽在不言（注释）之中.**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        //存储点
        static List<point> list = new ArrayList<>();
        //全部判断是否找到路径
        static boolean flag = false;
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] maze = new int[n][m];
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < m; j++) {
        
                    maze[i][j] = sc.nextInt();
                }
            }
            dfs(maze, 0, 0);
            for (point p : list) {
        
                System.out.println("(" + p.x + "," + p.y + ")");
            }
        }
    
        public static void dfs(int[][] maze, int x, int y) {
        
            int row = maze.length;
            int col = maze[0].length;
            //判断是否到终点
            if (x + 1 == row && y + 1 == col) {
        
                list.add(new point(x, y));
                flag = true;
                return;
            }
            //判断下标是否合法
            if (x < 0 || x == row || y < 0 || y == col || flag) {
        
                return;
            }
            //如果不是墙壁 则可以搜索
            if (maze[x][y] == 0) {
        
                maze[x][y] = 1;
                list.add(new point(x, y));
                //四个方向搜索
                dfs(maze, x - 1, y);
                dfs(maze, x + 1, y);
                dfs(maze, x, y - 1);
                dfs(maze, x, y + 1);
                /**
                 * 这个地方是真的栓Q了我 没写if判断 程序执行完每次给我剩一个(0,0)
                 * 找到最后的路径了 但是添加的节点全被回溯删掉了 所以要在这里判断一下是否找到 
                 * 如果找到了 那么list的节点就不需要被回溯删除了 就这一个地方 哇敲 害得我调试
                 * 递归 一层一层看 呜呜呜
                 */
                if (!flag) {
        
                    maze[x][y] = 0;
                    list.remove(list.size() - 1);
                }
            }
        }
    
        static class point {
        
            int x;
            int y;
    
            public point() {
        
            }
    
            public point(int x, int y) {
        
                this.x = x;
                this.y = y;
            }
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/72a99e28381a407991f2c96d8cb238ab
[Link 2]: https://blog.csdn.net/qq_53130059/article/details/129541804?spm=1001.2014.3001.5501
[Link 3]: https://www.nowcoder.com/questionTerminal/cf24906056f4488c9ddb132f317e03bc