php做网站主题,程序员和网站开发,网络服务器功能的概述,网站定制营销的过程目录
一、年终奖
二、迷宫问题 一、年终奖
题目描述#xff1a; 小东所在公司要发年终奖#xff0c;而小东恰好获得了最高福利#xff0c;他要在公司年会上参与一个抽奖游戏#xff0c;游戏在一个6*6的棋盘上进行#xff0c;上面放着36个价值不等的礼物#xff0c; 每…目录
一、年终奖
二、迷宫问题 一、年终奖
题目描述 小东所在公司要发年终奖而小东恰好获得了最高福利他要在公司年会上参与一个抽奖游戏游戏在一个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],既第一格 是可以走的路。 数据范围2n,m10 输入的内容只包含0val1 输入描述 输入两个整数分别表示二维数组的行数列数。再输入相应的数组其中的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];ListListInteger ans new ArrayList();dfs(maze, flag, row, col, 0, 0, ans);for (int i 0; i ans.size(); i) {ListInteger 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, ListListInteger ans){//边界if(x 0 || x row || y 0 || y col){return false;}//位置没走过且是通路if(maze[x][y] 0 !flag[x][y]){ListInteger 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;}
}
如有建议或想法欢迎一起讨论学习~
