【Java版oj】day23年终奖、迷宫问题

淡淡的烟草味﹌ 2024-03-24 13:22 54阅读 0赞

**目录**

一、年终奖

（1）原题再现

（2）问题分析

（3）完整代码

二、迷宫问题

（1）原题再现

（2）问题分析

（3）完整代码

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

> ## 一、年终奖 ##
> 
> ### （1）原题再现 ###
> 
> [年终奖\_牛客题霸\_牛客网][Link 1]
> 
> **描述**
> 
> 小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6\*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
> 
> 给定一个6\*6的矩阵**board**，其中每个元素为对应格子的礼物价值,左上角为\[0,0\],请返回能获得的最大价值，保证每个礼物价值大于100小于1000
> 
> ### （2）问题分析 ###
> 
> **方法：动态规划**  
> **子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的最大价值  
> F(i,j): 从(0,0)到达F(i,j)的最大金额  
> 状态递推：  
> F(i,j) = min\{F(i-1,j) , F(i,j-1)\} + (i,j)  
> 初始化：  
> F(0,0) = (0,0)  
> 特殊情况：第0行和第0列  
> F(0,i) = F(0,i-1) + (0,i)  
> F(i,0) = F(i-1,0) + (i,0)  
> 返回结果：  
> F(m-1,n-1)**  
> 
> 
> 本题是最基本的动态规划题，因为每次只能向下或者向右移动一步，如何到达位置(i,j)，必然是由（i-1,j）或者（i,j-1）位置到达的。所以只要比较这两处位置的价值谁大就可以了。
> 
>  **初始化是关键！第一行代表一值向右走，价值是每个位置处的价值的累加。第一列代表一直向下走，价值也是每个位置处的价值的累加。**
> 
> ### （3）完整代码 ###
> 
>     import java.util.Iterator;
>     
>     /*
>      * 年终奖
>      */
>     public class Bonus {
>         public int getMost(int[][] board) {
>             // write code here
>             int row = board.length;
>             int col = board[0].length;
>             for (int i = 1; i < row; i++) {
>                 if (board[i][0] <= 100 || board[i][0] >= 1000) {
>                     break;
>                 }
>                 board[i][0] = board[i - 1][0] + board[i][0];
>             }
>             for (int i = 1; i < col; i++) {
>                 if (board[0][i] <= 100 || board[0][i] >= 1000) {
>                     break;
>                 }
>                 board[0][i] = board[0][i - 1] + board[0][i];
>             }
>             for (int i = 1; i < row; i++) {
>                 for (int j = 1; j < col; j++) {
>                     if (board[i][j] <= 100 || board[i][j] >= 1000) {
>                         break;
>                     }
>                     board[i][j] = Math.max(board[i][j - 1] + board[i][j], board[i - 1][j] + board[i][j]);
>     
>                 }
>             }
>             return board[row - 1][col - 1];
>         }
>     }
> 
> ![2bfac13da22f4eb483df1d2e149997b0.png][]

> ## 二、迷宫问题 ##
> 
> ### （1）原题再现 ###
> 
> [迷宫问题\_\_牛客网][Link 2]
> 
> 定义一个二维数组 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\],既第一格是可以走的路。
> 
> **输入描述:**
> 
> 输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的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)
> 
> 说明
> 
> 注意：不能斜着走！！
> 
> ### （2）问题分析 ###
> 
> 迷宫问题是BFS广度优先搜索的经典问题。假设是一个10\*10的迷宫，入口在(1,1)的位置，出口在(8,10)的位置，通过(1,1)一步可以走到的位置有两个(1,2)，(2,1)但是这两个点并不是出口，需要继续通过这两个位置进一步搜索，假设现在在(1,2),下一次一步可以到达的新的位置为(1,3)，(2,2)。而通过（2，1）可以一步到达的新的位置为（2，2），（3，1），但是这里（2，2）是重复的，所以每一个点在走的过程中需要标记是否已经走过了。两步之后，还没没有走到出口，这时候需要通过新加入的点再去探索下一步能走到哪些新的点上，重复这个过程，直到走到出口为止。代码解析这个过程，最关键的步骤用当前位置带出新的位置，新的位置可以存放在一个vector或者队列中。位置需要用坐标表示，这里封装出一个Pair。
> 
>  **具体的理解可以看我的代码，每一步都写了很详细。使用前驱结点的原因如下图，是为了找到路径。**
> 
> ![0ed1aa2e7de040de83fd3e0135d1ca49.png][]
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     /*
>      * 迷宫问题
>      */
>     class Pair { //坐标
>         int x;
>         int y;
>         Pair father;
>         public Pair(int x, int y, Pair father) {
>     
>             this.x = x;
>             this.y = y;
>             this.father = father;//前驱结点，定义这个用来保存经过的路径
>         }
>     }
>     
>     public class Main {
>     //根据题目要求，转换输出格式
>         public static String toStr(int curx, int cury) {
>             StringBuilder sb = new StringBuilder();
>             sb.append("(" + curx + "," + cury + ")");
>             return sb.toString();
>         }
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             int row = sc.nextInt();
>             int col = sc.nextInt();
>             int [][]array = new int [row][col];
>     //输入迷宫
>             for (int i = 0; i < row; i++) {
>                 for (int j = 0; j < col; j++) {
>                     array[i][j] = sc.nextInt();
>                 }
>             }
>     //迷宫只能走上下左右
>             int [][]fourLocation = {
>         {0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 
>             int [][] flag = new int[row][col]; //标记是否被走过
>     //队列用来存储迷宫的位置
>             Deque<Pair> queue = new LinkedList<>();
>     //放置路径
>             Stack<Pair> stack = new Stack<>();
>     
>             queue.offer(new Pair(0, 0, null));
>             flag[0][0] = 1; //走过标记为1
>             int temp = 0; //判断是否在目标位置。即右下角
>             Pair curLocation = null;
>             while (!queue.isEmpty()) {
>                 curLocation = queue.poll();
>     //当前位置带出所有新的位置, 可以向上下左右走
>                 for (int i = 0; i < 4; i++) {
>     //计算新的位置
>                     int curX = curLocation.x;
>                     int curY = curLocation.y;
>     
>                     int newX = curX + fourLocation[i][0]; //x轴
>                     int newY = curY + fourLocation[i][1]; //y轴
>     //位置越界，继续计算下一个位置
>                     if (newX < 0 || newX >= row || newY < 0 || newY >= col) {
>                         continue;
>                     }
>     //如果新的位置无障碍并且之前也没走过，保存新的位置
>                     if (array[newX][newY] == 0 && flag[newX][newY] == 0) {
>     //找到新位置和新位置前驱位置（上一个位置）
>                         Pair newLocation = new Pair(newX, newY, curLocation);
>                         queue.offer(newLocation);
>                         flag[newX][newY] = 1;
>     
>                     }
>     //如果新的位置为目标位置,则结束查找
>                     if (newX == row - 1 && newY == col - 1) {
>                         temp = 1; //到达目标位置
>                         break;
>                     }
>                 }
>     
>                 if (temp == 1) {
>                     break;
>                 }
>             }
>     //将路径入栈，先进后出原则，最后的一个位置先入栈，故而最后一个出来
>             while (curLocation != null) {
>                 stack.push(curLocation);
>                 curLocation = curLocation.father;
>             }
>     //将栈中路径按要求输出
>             while (!stack.isEmpty()) {
>                 System.out.println(toStr(stack.peek().x, stack.peek().y));
>                 stack.pop();
>             }
>     //因为是将前驱位置入栈，所以栈中位置只到目标位置的前一个位置。
>             System.out.println(toStr(row-1, col-1));
>         }
>     }
> 
> ![c95ebdca9c104d838084a19f0bdbf5c8.png][]

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

![c2ec50cfd2454c89bb08a2f8791752a8.png][]

[Link 1]: https://www.nowcoder.com/practice/72a99e28381a407991f2c96d8cb238ab?tpId=49&&tqId=29305&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[2bfac13da22f4eb483df1d2e149997b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/70ec01e7ae4641fe91e454fc9f537c42.png
[Link 2]: https://www.nowcoder.com/questionTerminal/cf24906056f4488c9ddb132f317e03bc?f=discussion
[0ed1aa2e7de040de83fd3e0135d1ca49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3177f452b02e4172974d6ba70d821f07.png
[c95ebdca9c104d838084a19f0bdbf5c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e81bcf942af04303852f3d53398c305d.png
[c2ec50cfd2454c89bb08a2f8791752a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/27969c9721a143b0992d722ea8cd20de.png