Title: * ~ year end bonus

Title Description
Xiaodong's company will give a year-end bonus, and Xiaodong happens to get the highest welfare. He will participate in a lucky draw game at the company's annual meeting. The game is played on a 6 * 6 chessboard with 36 gifts of different values on it. There is a gift on each small chessboard. He needs to start the game from the upper left corner and can only move down or right one step at a time, Stop at the lower right corner and Xiaodong can get all the gifts in the grid along the way. Please design an algorithm to make Xiaodong get the gift with the highest value.

Given a 6 * 6 matrix board, where each element is the gift value of the corresponding grid, and the upper left corner is [0,0], please return the maximum value that can be obtained to ensure that each gift value is greater than 100 and less than 1000.

Solution:
Question: what is the maximum value that Xiaodong can obtain
Sub problem: Xiaodong's maximum value when walking to a grid
State F(j): the maximum value when Xiaodong walks to (j) grid
Transfer equation: F(j)= max(F(i-1,j), F(ij- 1)) + board[i1j]
First line: F(0,j): F(0,j-1)
First column: F(i,0):F(i-1,0)

import java.util.*;

public class Bonus {
    public int getMost(int[][] board) {
        int m=board.length;
        int n=board[0].length;
        for(int i=1;i<m;i++){
           board[i][0]+=board[i-1][0];
        }
        for(int j=1;j<n;j++){
            board[0][j]+=board[0][j-1];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                board[i][j]+=Math.max(board[i-1][j],board[i][j-1]);
            }
            
        }
        return board[m-1][n-1];
    }
}

Title: * ~ maze problem

The title description defines a two-dimensional array N*M (where 2 < = n < = 10; 2 < = m < = 10), such as 5 × 5. The array is shown below:

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1,1, 1, 0,
0, 0, 0, 1, 0, };

It represents a maze, in which 1 represents the wall and 0 represents the road that can be taken. You can only walk horizontally or vertically, not diagonally. It is required to program to find the shortest route from the upper left corner to the lower right corner. The entry point is [0,0], that is, the first space is the way to go.

This question contains multiple groups of data.

Enter Description:
Enter two integers to represent the number of rows and columns of the binary array respectively. Then enter the corresponding array, where 1 represents the wall and 0 represents the road that can be taken. The data is guaranteed to have a unique solution, regardless of multiple solutions, that is, there is only one channel in the maze.

Output Description: the shortest path from the upper left corner to the lower right corner. The format is shown in the example.

import java.util.*;
public class Main {
   public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while(scan.hasNext()) {
                int row = scan.nextInt();
                int col = scan.nextInt();
                int[][] arr = new int[row][col];
                for(int i = 0; i < row; i++)
                    for(int j = 0; j < col; j++)
                        arr[i][j] = scan.nextInt();
                check(arr, 0, 0);//Detect the maze in advance and set the impassable road to 1
                System.out.println(mazePath(arr, 0, 0));//Formal maze
            }
        }
        public static int check(int[][] arr, int x, int y) {
            //If it's the exit in the lower right corner
            if(x == arr.length - 1 && y == arr[x].length - 1) return 1;
            //If the current location is a road
            if(x < arr.length && y < arr[arr.length - 1].length && arr[x][y] == 0) {
                //If the next step is death
                if(check(arr, x + 1, y) == -1 && check(arr, x, y + 1) == -1) {
                    //Seal this position
                    arr[x][y] = 1;
                    return -1;
                }else return 1;
                //If the current location is not a road
            }else return -1;
        }
        public static String mazePath(int[][] arr, int x, int y) {
            //If it is the exit in the lower right corner, return the coordinates
            if(x == arr.length - 1 && y == arr[x].length - 1) return "(" + x + "," + y + ")";
            //If the current position is a road, return to the coordinates and move on
            if(x < arr.length && y < arr[arr.length - 1].length && arr[x][y] == 0) return "(" + x + "," + y + ")" + "\n" + mazePath(arr, x + 1, y) + mazePath(arr, x, y + 1);
                //If the current position is not a road, do nothing
            else return "";
        }
}