1.杭电：nightmare

讲解：B18 双向BFS Nightmare_哔哩哔哩_bilibili

package com.jachem;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Nightmare {

    // Directions for moving: right, down, left, up
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int n, m;
    static char[][] maze;
    static int[][] ghost;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
        sc.close();
    }

    public static void solve(Scanner sc) {
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // Consume the rest of the line after reading n and m

        maze = new char[n][m];
        boolean[][] vis_b = new boolean[n][m]; // Visited by boy
        boolean[][] vis_g = new boolean[n][m]; // Visited by girl

        Queue<int[]> qb = new LinkedList<>(); // Boy's queue
        Queue<int[]> qg = new LinkedList<>(); // Girl's queue

        int[] boyStart = new int[2];
        int[] girlStart = new int[2];
        ghost = new int[2][2];
        int ghostCount = 0;

        for (int i = 0; i < n; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < m; j++) {
                maze[i][j] = line.charAt(j);
                if (maze[i][j] == 'M') {
                    boyStart[0] = i;
                    boyStart[1] = j;
                } else if (maze[i][j] == 'G') {
                    girlStart[0] = i;
                    girlStart[1] = j;
                } else if (maze[i][j] == 'Z') {
                    ghost[ghostCount][0] = i;
                    ghost[ghostCount++][1] = j;
                }
            }
        }

        // Add initial positions to queues and mark as visited
        qb.offer(boyStart);
        vis_b[boyStart[0]][boyStart[1]] = true;
        qg.offer(girlStart);
        vis_g[girlStart[0]][girlStart[1]] = true;

        int time = 0;
        while (!qb.isEmpty() && !qg.isEmpty()) {
            time++;

            // Boy's turn: 3 steps
            for (int step = 0; step < 3 && !qb.isEmpty(); step++) {
                int size = qb.size();
                for (int i = 0; i < size; i++) {
                    int[] curr = qb.poll();
                    if(!isSafe(curr[0], curr[1], time))continue;
                    // The person might get caught by a ghost while waiting, but the problem implies
                    // we only check for safety upon moving to a *new* cell.
                    // Let's stick to checking the destination cell.

                    for (int k = 0; k < 4; k++) {
                        int nx = curr[0] + dx[k];
                        int ny = curr[1] + dy[k];

                        if (isSafe(nx, ny, time) && !vis_b[nx][ny]) {
                            vis_b[nx][ny] = true;
                            // Check if this new spot has been visited by the girl
                            if (vis_g[nx][ny]) {
                                System.out.println(time);
                                return;
                            }
                            qb.offer(new int[]{nx, ny});
                        }
                    }
                }
            }

            // Girl's turn: 1 step
            // The step loop is not strictly necessary for 1 step, but keeps the structure similar
            for (int step = 0; step < 1 && !qg.isEmpty(); step++) {
                int size = qg.size();
                for (int i = 0; i < size; i++) {
                    int[] curr = qg.poll();
                    if(!isSafe(curr[0], curr[1], time))continue;
                    for (int k = 0; k < 4; k++) {
                        int nx = curr[0] + dx[k];
                        int ny = curr[1] + dy[k];

                        if (isSafe(nx, ny, time) && !vis_g[nx][ny]) {
                            vis_g[nx][ny] = true;
                            // Check if this new spot has been visited by the boy
                            if (vis_b[nx][ny]) {
                                System.out.println(time);
                                return;
                            }
                            qg.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
        }

        // If the loop finishes, it means one queue became empty and they never met.
        System.out.println(-1);
    }

    /**
     * Checks if a cell (x, y) is safe to enter at a given time.
     * A cell is safe if it's within bounds, not a wall, and not within the ghost's reach.
     */
    private static boolean isSafe(int x, int y, int time) {
        // Check bounds
        if (x < 0 || x >= n || y < 0 || y >= m) {
            return false;
        }
        // Check for walls
        if (maze[x][y] == 'X') {
            return false;
        }
        // Check for ghosts
        for (int i = 0; i < 2; i++) {
            int dist = Math.abs(ghost[i][0] - x) + Math.abs(ghost[i][1] - y);
            if (dist <= time * 2) {
                return false;
            }
        }
        return true;
    }
}

2.洛谷U311289 矩阵距离

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// OJ提交时类名必须为Main
public class Main {
    public static void main(String[] args) throws IOException {
        // 依然使用BufferedReader进行高效IO
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] dis = new int[n][m];
        
        // 关键改动(1): 使用原始int数组模拟队列
        int[] queue = new int[n * m];
        // 关键改动(2): 定义队头和队尾指针
        int head = 0, tail = 0;

        // 初始化距离矩阵，并将初始'1'的位置入队
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                if (line.charAt(j) == '1') {
                    // 关键改动(3): 入队操作
                    // 将压缩后的坐标存入数组，并移动队尾指针
                    queue[tail++] = i * m + j; 
                    dis[i][j] = 0;
                } else {
                    dis[i][j] = -1; // 标记为未访问
                }
            }
        }

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

        // BFS主循环
        // 关键改动(4): 判空操作
        while (head < tail) {
            // 关键改动(5): 出队操作
            // 取出队头元素，并移动队头指针
            int currentIdx = queue[head++];
            
            // 解压坐标
            int x = currentIdx / m;
            int y = currentIdx % m;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && dis[nx][ny] == -1) {
                    dis[nx][ny] = dis[x][y] + 1;
                    // 关键改动(6): 新元素入队
                    queue[tail++] = nx * m + ny;
                }
            }
        }

        // 高效输出
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(dis[i][j]);
                if (j < m - 1) {
                    sb.append(" ");
                }
            }
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }
}

后记：bufferReader AND StringTokenizer

1)bufferReader

它的核心思想是：

想象一下，你家水龙头的水流很小，你要接一大桶水。如果每次都只用一个小杯子去接一点，然后倒进桶里，来来回回会非常慢。一个聪明的办法是，先在水龙头下放一个大水桶，等水桶接满了，再一口气把整桶水倒进你的最终容器里。这样效率就高多了。

BufferedReader 就是这个“大水桶”。

• 不带缓冲（如 System.in.read()）：每当你需要一个字符，程序就向操作系统请求一次数据。这种频繁的系统调用（I/O操作）是非常昂贵的，就像用小杯子接水。

• 带缓冲（BufferedReader）：当你第一次请求数据时，BufferedReader 会一次性从底层输入源（比如键盘、文件）读取一大块数据（默认缓冲区大小是8192个字符，即8KB）到它内部的内存缓冲区中。之后，当你再需要数据时，它会直接从这个内存缓冲区里给你，而不是每次都去麻烦操作系统。只有当缓冲区的数据用完了，它才会再次进行昂贵的I/O操作，去“接下一桶水”。

bufferReader教程：Java 流(Stream)、文件(File)和IO | 菜鸟教程

简要说明：

// System.in 是一个 InputStream (字节流)
// InputStreamReader 是一个适配器，将字节流转换为字符流
// BufferedReader 包装字符流，提供缓冲功能
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

// 读取一整行数据
String line = br.readLine(); // 注意: 这个方法可能会抛出 IOException，所以主函数需要声明

StringTokenizer

是一个经典工具，属于 java.util 包。它专门用来分割字符串。

它的核心思想是：

当你用 String.split() 方法时，它会使用正则表达式来分割字符串，这功能强大但性能开销较大。更重要的是，split()会一次性把所有分割好的子字符串都创建出来，并存入一个字符串数组。如果一行数据很长，有成千上万个数字，那么一次性创建这么多字符串对象和数组对象，会消耗大量时间和内存。

StringTokenizer 则采用了一种“懒加载”或者说“迭代器”的模式。

1）它不会一次性分割所有部分。

2）当你调用 nextToken() 时，它才会在原始字符串上找到下一个分隔符，并返回这中间的子字符串。它内部只维护一些指针来记录当前处理到哪里了。

//通常和 BufferedReader 配合使用，先读一行，再用 StringTokenizer 分割。
// 假设已经用 br.readLine() 读到了一行 "10 20"
String line = br.readLine();

// 使用空格作为默认分隔符来创建 StringTokenizer
StringTokenizer st = new StringTokenizer(line);

// 检查是否还有下一个部分
if (st.hasMoreTokens()) {
    // 获取下一个部分并转换为整数
    int n = Integer.parseInt(st.nextToken());
}
if (st.hasMoreTokens()) {
    int m = Integer.parseInt(st.nextToken());
}

性能对比：Scanner vs. BufferedReader + StringTokenizer

特性	Scanner	BufferedReader + StringTokenizer
读取机制	同步 + 正则解析。Scanner为了支持读取不同类型（nextInt, nextDouble），内部需要进行复杂的正则匹配和类型转换，这非常慢。	异步 + 缓冲。BufferedReader一次性读取大块数据到内存，readLine()直接从内存返回，速度极快。
内存使用	高。Scanner 内部有一个较大的缓冲区（默认1KB），并且其复杂的解析机制会创建额外的临时对象。在处理大规模输入时，这些累积的内存占用可能导致MLE。	低。BufferedReader 的缓冲区是固定大小的，并且StringTokenizer是轻量级的，不会一次性创建所有子字符串，内存控制得更好。
易用性	高。API非常友好，可以直接用 nextInt(), nextDouble() 等方法，不需要手动做类型转换。	低。需要手动处理 IOException，并且需要自己调用 Integer.parseInt() 或 Double.parseDouble() 进行类型转换。代码写起来更繁琐。
适用场景	适合快速原型开发、小程序、或对性能和内存要求不高的场景。	算法竞赛、处理大文件、对性能和内存有严格要求的场景。这是Java选手在竞赛中的标配。

2)StringTokenizer 的构造函数

StringTokenizer 主要有三个构造函数：

1. StringTokenizer(String str)

   • 这是最简单的构造函数。

   • 它会使用默认的分隔符集，包括：

     • 空格 (' ')

     • 制表符 ('\t')

     • 换行符 ('\n')

     • 回车符 ('\r')

     • 换页符 ('\f')

   • 示例：StringTokenizer st = new StringTokenizer("hello world\tjava"); 会将字符串分割成 "hello", "world", "java" 三个部分。

2. StringTokenizer(String str, String delim)

   • 这是最常用的自定义分隔符的构造函数。

   • str: 要被分割的源字符串。

   • delim: 一个包含所有分隔符的字符串。delim 字符串中的每一个字符都会被当作一个独立的分隔符。

   • 示例 1：使用逗号分割

     Generated java

           String data = "apple,banana,orange";
     // 将逗号 , 作为分隔符
     StringTokenizer st = new StringTokenizer(data, ",");
     while (st.hasMoreTokens()) {
         System.out.println(st.nextToken());
     }
     // 输出:
     // apple
     // banana
     // orange
         

   • 示例 2：使用多个字符作为分隔符

     Generated java

           String data = "level-1;stage-A,round-3";
     // 将 - ; , 这三个字符都视为分隔符
     StringTokenizer st = new StringTokenizer(data, "-;,");
     while (st.hasMoreTokens()) {
         System.out.println(st.nextToken());
     }
     // 输出:
     // level
     // 1
     // stage
     // A
     // round
     // 3
         

     IGNORE_WHEN_COPYING_START

     content_copydownload

     Use code with caution. Java

     IGNORE_WHEN_COPYING_END

     注意：StringTokenizer 不会将 "-;," 整个字符串视为一个分隔符，而是将 -、;、, 分别视为分隔符。这是它和 String.split() 的一个重要区别。

3. StringTokenizer(String str, String delim, boolean returnDelims)

   • 这个构造函数增加了一个布尔参数 returnDelims。

   • 如果 returnDelims 为 true，那么分隔符本身也会被 nextToken() 当作一个token返回。

   • 这在需要处理分隔符本身的场景下很有用。

   • 示例：

     Generated java

           String data = "a+b=c";
     // 将 + 和 = 作为分隔符，并且返回分隔符本身
     StringTokenizer st = new StringTokenizer(data, "+=", true);
     while (st.hasMoreTokens()) {
         System.out.println(st.nextToken());
     }
     // 输出:
     // a
     // +
     // b
     // =
     // c
         

     IGNORE_WHEN_COPYING_START

     content_copydownload

     Use code with caution. Java

     IGNORE_WHEN_COPYING_END

     如果 returnDelims 为 false（默认情况），输出则会是 a, b, c。

要在 StringTokenizer 中指定其他分隔符，最直接的方法就是使用第二个构造函数：new StringTokenizer(yourString, yourDelimiters)。只需将所有你希望用作分隔符的字符拼接成一个字符串传给 yourDelimiters 参数即可。