Huawei computer test: Student matrix

【 Programming topics |200 branch 】 Student matrix 【2022 Q2 Examination questions 】

Title Description

• The school organizes activities , Arrange the students into a rectangular array .
• Please find the largest number of boys connected in the rectangular array .
• This connecting position is in a straight line , The direction can be horizontal , Vertical , Diagonal or anti diagonal .
• notes ： The number of students will not exceed 10000

Input description

• The number of rows and columns of the input first row matrix , Next n Behavior matrix elements , Between elements ”,” Separate .

Output description

• Output an integer , Represents the number of boys connected at the longest position in the matrix .

Example

Input

3,4
F,M,M,F
F,M,M,F
F,F,F,M

Output

3

Input

1,2
M,M

Output

2

Input

2,1
M
F

Output

1

Thought analysis

Method 1 ： Dynamic programming

This problem sees the square matrix , The next grid is related to the next grid , Sideways 、 Vertical 、 Diagonals 、 Anti diagonal , You can think of the solution of dynamic programming .

But here's the thing , Four situations should be considered separately , Carry out dynamic planning respectively ：

1. Initialize the first row and first column , Look in the lower right corner , It can be counted horizontally , Vertical , The maximum value of diagonal .
2. Initialize the first line , The last column , Look in the lower left corner , You can count the maximum value of the inverse diagonal .

If the overall dynamic planning , The horizontal will affect the vertical , such as

3,4
F,M,M,F
F,M,M,F
F,F,F,F

If direct overall dynamic planning , There will be interference , There will be repeated addition

dp[i][j] = Math.max(dp[i - 1][j], Math.max(dp[i][j - 1), dp[i - 1][j - 1]) + 1;

Therefore, we need to separate four directions for Dynamic Planning , Finally, calculate the maximum values in four directions .

Another thing to note is , When initializing an array , If for the first line , First column , Or the last column , encounter "M", Initialize to 1 when , When there is only one row or one column , There will be no statistics , Therefore, it is necessary to deal with special situations , One row or one column is processed separately .

Method 2 ： simulation

Discuss the longest number in these four cases .

Reference code

Method 1 ： Dynamic programming

import java.util.Scanner;
public class studentFangZhen {
    
    public static void main(String[] args) {
    
        Scanner in = new Scanner(System.in);
        String[] str1 = in.nextLine().split(",");
        int m = Integer.parseInt(str1[0]);
        int n = Integer.parseInt(str1[1]);
        String[][] s = new String[m][n];
        for (int i = 0; i < m; i++) {
    
            String[] s1 = in.nextLine().split(",");
            for (int j = 0; j < n; j++) {
    
                s[i][j] = s1[j];
            }
        }
        int[][] dp1 = new int[m][n];  //  From left to right 
        int[][] dp2 = new int[m][n];  //  From the top down 
        int[][] dp3 = new int[m][n];  //  Diagonals 
        int[][] dp4 = new int[m][n];  //  Anti diagonal 
        //  special case , There is only one row or one column , You can't give every one equal to M The initialization of is 1, Also consider the previous situation 
        int ans = 0;
        if (m == 1) {
    
            if (s[0][0].equals("M")) {
    
                dp1[0][0] = 1;
            }
            for (int j = 1; j < n; j++) {
    
                if (s[0][j - 1].equals("M")) {
    
                    if (s[0][j].equals("M")) {
    
                        dp1[0][j] = dp1[0][j - 1] + 1;
                    }
                } else {
    
                    if (s[0][j].equals("M")){
    
                        dp1[0][j] = 1;
                    }
                }
            }
            for (int j = 0; j < n; j++) {
    
                ans = Math.max(ans, dp1[0][j]);
            }
            System.out.println(ans);
            return;
        }
        if (n == 1) {
    
            if (s[0][0].equals("M")) {
    
                dp2[0][0] = 1;
            }
            for (int i = 1; i < m; i++) {
    
                if (s[i - 1][0].equals("M")) {
    
                    if (s[i][0].equals("M")) {
    
                        dp2[i][0] = dp2[i - 1][0] + 1;
                    }
                } else {
    
                    if (s[i][0].equals("M")) {
    
                        dp2[i][0] = 1;
                    }
                }
            }
            for (int i = 0; i < m; i++) {
    
                ans = Math.max(ans, dp2[i][0]);
            }
            System.out.println(ans);
            return;
        }
        //  initialization dp1, dp2, dp3, dp4 Array 
        for (int i = 0; i < m; i++) {
    
            if (s[i][0].equals("M")) {
    
                dp1[i][0] = 1;
                dp2[i][0] = 1;
                dp3[i][0] = 1;
            }
        }
        for (int j = 0; j < n; j++) {
    
            if (s[0][j].equals("M")) {
    
                dp1[0][j] = 1;
                dp2[0][j] = 1;
                dp3[0][j] = 1;
                dp4[0][j] = 1;
            }
        }
        //  initialization dp4 Array 
        for (int i = 0; i < m; i++) {
    
            if (s[i][n - 1].equals("M")) {
    
                dp4[i][n - 1] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
    
            for (int j = 1; j < n; j++) {
    
                if (s[i][j].equals("M")) {
    
                    if (s[i][j - 1].equals("M")) {
     //  From left to right 
                        dp1[i][j] = dp1[i][j - 1] + 1;
                    }
                    if (s[i - 1][j].equals("M")) {
      //  From the top down 
                        dp2[i][j] = dp2[i - 1][j] + 1;
                    }
                    if (s[i - 1][j - 1].equals("M")) {
     //  Diagonals 
                        dp3[i][j] = dp3[i - 1][j - 1] + 1;
                    }
                }
            }
        }
        for (int i = 1; i < m; i++) {
    
            for (int j = n - 2; j >= 0; j--) {
    
                if (s[i][j].equals("M")) {
    
                    if (s[i - 1][j + 1].equals("M")) {
     //  Anti diagonal 
                        dp4[i][j] = dp4[i - 1][j + 1] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
      //  Take the maximum of the four arrays 
            for (int j = 0; j < n; j++) {
    
                ans = Math.max(ans, Math.max(dp1[i][j], Math.max(dp2[i][j], Math.max(dp3[i][j], dp4[i][j]))));
            }
        }
        System.out.println(ans);
    }
}

It's complicated to write it down like this , Welcome to discuss in the comment area and leave a simpler algorithm .

Method 2 ： simulation

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class StudentFangZhen2 {
    
    public static void main(String[] args) {
    
        Scanner in = new Scanner(System.in);
        String[] str1 = in.nextLine().split(",");
        int m = Integer.parseInt(str1[0]);
        int n = Integer.parseInt(str1[1]);
        String[][] s = new String[m][n];
        for (int i = 0; i < m; i++) {
    
            String[] s1 = in.nextLine().split(",");
            for (int j = 0; j < n; j++) {
    
                s[i][j] = s1[j];
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (s[i][j].equals("M")) {
    
                    getResult(s, i, j, list);
                }
            }
        }
        Collections.sort(list);
        System.out.println(list.get(list.size() - 1));
    }
    public static void getResult(String[][] s, int i, int j, List<Integer> list) {
    
        int len = 1;
        int a = 0, b = 0;
        int m = s.length, n = s[0].length;
        if (j < n) {
      //  From left to right 
            a = i;
            b = j;
            while (b < n - 1 && s[a][++b].equals("M")) {
    
                len++;
            }
            list.add(len);
            len = 1;
        }
        if (i < m) {
      //  From the top down 
            a = i;
            b = j;
            while (a < m - 1 && s[++a][b].equals("M")) {
    
                len++;
            }
            list.add(len);
            len = 1;
        }
        if (i < m && j < n) {
      //  Diagonals 
            a = i;
            b = j;
            while ((a < m - 1 && b < n - 1) && s[++a][++b].equals("M")) {
    
                len++;
            }
            list.add(len);
            len = 1;
        }
        if (i >= 0 && j < n) {
      //  From left to right 
            a = i;
            b = j;
            while (( a > 0 && b < n - 1) && s[--a][++b].equals("M")) {
    
                len++;
            }
            list.add(len);
        }
    }
}

Welcome to comment and leave your own more concise method .