48Days-Day19 | ISBN号，kotori和迷宫，矩阵最长递增路径

ISBN号

ISBN号码_牛客题霸_牛客网

算法原理

模拟，根据题意模拟就可以了，注意一下余数为10的时候要特别判断一下是不是X就行了

代码

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        char[] s = scan.next().toCharArray();
        int sum = 0, count = 0;
        for(int i = 0; i < s.length - 1; i++) {
            if(i == 1 || i == 5 || i == 11) continue;
            count++;
            sum += (s[i] - '0') * count;
        }

        boolean flg = false;
        if(s[s.length - 1] == 'X') flg = (sum % 11 == 10);  //特别判断一下为10的情况
        else flg = (sum % 11 == s[s.length - 1] - '0');

        if(flg) System.out.println("Right");
        else {
            if(sum % 11 == 10) s[s.length - 1] = 'X';
            else s[s.length - 1] = Character.forDigit(sum % 11, 10);
            StringBuffer sb = new StringBuffer();
            for(char x: s) sb.append(x);
            System.out.println(sb.toString());
        }
    }
}

kotori和迷宫

kotori和迷宫

算法原理

迷宫类最短路径dfs问题的扩展，原理都差不多，就是最后输出的时候单独要多记录一下出口数量而已

代码

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int N = 35;
    public static int x1, y1;  //记录起点位置
    public static int n, m;
    public static char[][] arr = new char[N][N];
    public static int[][] dist = new int[N][N];

    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1, -1, 0, 0};

    public static void bfs() {
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                dist[i][j] = -1;
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x1, y1});
        dist[x1][y1] = 0;

        while(!q.isEmpty()) {
            int[] tmp = q.poll();
            int a = tmp[0], b = tmp[1];
            for(int i = 0; i < 4; i++) {
                //遍历该点的上下左右的四个点
                int x = a + dx[i], y = b + dy[i];
                //坐标是合法的，该点没有记录过，且不是墙
                if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1 && arr[x][y] != '*') {
                    dist[x][y] = dist[a][b] + 1;
                    if(arr[x][y] != 'e') {
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        m = scan.nextInt(); n = scan.nextInt();
        for(int i = 0; i < m; i++) {
            char[] tmp = scan.next().toCharArray();
            for(int j = 0; j < n; j++) {
                arr[i][j] = tmp[j];
                if(arr[i][j] == 'k') {
                    x1 = i; y1 = j;
                }
            }
        }

        bfs();

        int count = 0, res = 1000;    //count记录出口个数
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
                if(arr[i][j] == 'e' && dist[i][j] != -1) {    //为-1说明无法到达
                    count++;
                    res = Math.min(res, dist[i][j]);
                }
            }
        if(count == 0) System.out.println("-1");
        else System.out.println(count + " " + res);
    }
}

矩阵最长递增路径

矩阵最长递增路径_牛客题霸_牛客网

算法原理

递归 + 记忆搜索

代码

import java.util.*;


public class Solution {
    public static int m, n;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1, -1, 0, 0};
    public static int[][] memo = new int[1010][1010];

    public int dfs(int[][] matrix, int i, int j) {
        if (memo[i][j] != -1) return memo[i][j];

        int len = 1;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
                len = Math.max(len, 1 + dfs(matrix, x, y));
        }

        memo[i][j] = len;
        return len;
    }
    public int solve (int[][] matrix) {
        // write code here
        m = matrix.length;
        n = matrix[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                memo[i][j] = -1;
            }

        int res = 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                res = Math.max(res, dfs(matrix, i, j));
            }
        return res;
    }
}