2022/08/21字节后端笔试

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        cin.nextLine();

        int startI = 0, startJ = 0;
        char[][] grid = new char[n][];
        for (int i = 0; i < n; i++) {
            String line = cin.nextLine();
            grid[i] = line.toCharArray();
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'O') {
                    startI = i; startJ = j;
                }
            }
        }

        System.out.println(countLeft(grid, n, m, startI, startJ));
    }

    public static int countLeft(char[][] grid, int n, int m, int i, int j) {
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][m];

        q.offer(new int[]{i,j});
        visited[i][j] = true;

        while (!q.isEmpty()) {
            int[] currPoint = q.poll();
            int x = currPoint[0], y = currPoint[1];
            // 上，上一个字母必须是D或者.
            if (x - 1 >= 0 && !visited[x - 1][y]) {
                int newX = x - 1, newY = y;
                if (grid[newX][newY] == '.' || grid[newX][newY] == 'D') {
                    q.offer(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
            // 下，上一个字母必须是U或者.
            if (x + 1 < n && !visited[x + 1][y]) {
                int newX = x + 1, newY = y;
                if (grid[newX][newY] == '.' || grid[newX][newY] == 'U') {
                    q.offer(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
            // 左，上一个字母必须是R或者.
            if (y - 1 >= 0 && !visited[x][y - 1]) {
                int newX = x, newY = y - 1;
                if (grid[newX][newY] == '.' || grid[newX][newY] == 'R') {
                    q.offer(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
            // 右，上一个字母必须是L或者.
            if (y + 1 < m && !visited[x][y + 1]) {
                int newX = x, newY = y + 1;
                if (grid[newX][newY] == '.' || grid[newX][newY] == 'L') {
                    q.offer(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }

        int cannotReach = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (!visited[r][c])
                    cannotReach++;
            }
        }
        return cannotReach;
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        cin.nextLine();
        String pattern = cin.nextLine();
        StringBuilder sb = new StringBuilder();
        int idx = 0, len = pattern.length();
        while (idx < len) {
            char ch = pattern.charAt(idx);
            if (ch == '{') {
                while (idx < len && pattern.charAt(idx) != '}')
                    idx++;
                idx++;
                sb.append('*');
                if (idx < len)
                    sb.append(pattern.charAt(idx));
                idx++;
                continue;
            }
            sb.append(ch);
            idx++;
        }
        String p = sb.toString();

        for (int i = 0; i < n; i++) {
            String s = cin.nextLine();
            if (match(s, p))
                System.out.println("True");
            else
                System.out.println("False");
        }
    }

    public static boolean match(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*')
                dp[0][j] = true;
            else
                break;
        }

        for (int i = 1; i <= m; i++) {
            char a = s.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char b = p.charAt(j - 1);
                if (b == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else if (a == b) {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }

        return dp[m][n];
    }
}