一、kotori和气球

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long ans = n;
        for(int i = 1;i<m;i++){
            ans=(ans*(n-1))%109;
        }
        if(n==1&&m!=1) System.out.println(0);
        else System.out.println(ans);
    }
}

分析：

• 本题的推导过程：
  • 第 1 个位置：n 种选择
  • 第 2~m 个位置：每个位置都不能和前一个相同，所以有 n-1 种选择
  • 总方案数：n × (n-1)^(m-1)
• 这是排列组合里最基础的 “分步计数” 思想，也是这类 “相邻不同色 / 不同物” 问题的通用解法。

• 题目要求结果对 109 取模，考察了模运算的基本性质：

• (a × b) % mod = [(a % mod) × (b % mod)] % mod

1.输入两个整数

int n = sc.nextInt();
int m = sc.nextInt();

2.排列组合运算，模运算

long ans = n;
for(int i = 1;i<m;i++){
    ans=(ans*(n-1))%109;
}

3.排除特殊情况

if(n==1&&m!=1) System.out.println(0);
else System.out.println(ans);

二、走迷宫

深度优先搜素

Scanner scan = new Scanner(System.in);
String[] nm = scan.nextLine().split(" ");
int n = Integer.valueOf(nm[0].trim());
int m = Integer.valueOf(nm[1].trim());
String[] se = scan.nextLine().split(" ");
// 注意：题目坐标是1-based，代码中转为0-based索引
int xs = Integer.valueOf(se[0].trim()) - 1;
int ys = Integer.valueOf(se[1].trim()) - 1;
int xe = Integer.valueOf(se[2].trim()) - 1;
int ye = Integer.valueOf(se[3].trim()) - 1;

// 读取网格地图
char[][] matrix = new char[n][m];
for (int i = 0; i < n; i++) {
    char[] chrs = scan.nextLine().toCharArray();
    for (int j = 0; j < chrs.length; j++) {
        matrix[i][j] = chrs[j];
    }
}


//BFS 初始化
// 特殊情况：起点就是终点，直接返回0
if (xs == xe && ys == ye) {
    System.out.println(0);
    return;
}

// steps数组：记录每个格子到起点的最短步数，初始为0
int[][] steps = new int[n][m];
steps[xs][ys] = 0;

// 队列用于BFS，存储待遍历的坐标
Queue<int[]> queue = new LinkedList<>();
int[] tmp = new int[] {xs, ys};
queue.add(tmp);


//BFS 核心循环
while (!queue.isEmpty()) {
    tmp = queue.poll(); // 取出队首坐标
    if (tmp[0] == xe && tmp[1] == ye) {
        break; // 到达终点，直接跳出循环
    }

    // 四个方向的移动判断（上、下、左、右）
    // 向上移动（行号减1）
    if (tmp[0] - 1 >= 0 && tmp[0] - 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] - 1][tmp[1]] == '.') {
        int[] location = new int[] {tmp[0] - 1, tmp[1]};
        queue.add(location);
        steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
        matrix[tmp[0] - 1][tmp[1]] = '*'; // 标记为已访问，避免重复入队
    }
    // 向下移动（行号加1）
    if (tmp[0] + 1 >= 0 && tmp[0] + 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] + 1][tmp[1]] == '.') {
        int[] location = new int[] {tmp[0] + 1, tmp[1]};
        queue.add(location);
        steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
        matrix[tmp[0] + 1][tmp[1]] = '*';
    }
    // 向左移动（列号减1）
    if (tmp[0] >= 0 && tmp[0] < n && tmp[1] - 1 >= 0 && tmp[1] - 1  < m && matrix[tmp[0]][tmp[1] - 1] == '.') {
        int[] location = new int[] {tmp[0], tmp[1] - 1};
        queue.add(location);
        steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
        matrix[tmp[0]][tmp[1] - 1] = '*';
    }
    // 向右移动（列号加1）
    if (tmp[0] >= 0 && tmp[0] < n && tmp[1] + 1 >= 0 && tmp[1] + 1 < m && matrix[tmp[0]][tmp[1] + 1] == '.') {
        int[] location = new int[] {tmp[0], tmp[1] + 1};
        queue.add(location);
        steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
        matrix[tmp[0]][tmp[1] + 1] = '*';
    }
}

分析：

这是一道经典的无权网格最短路径问题，核心要求：

• 在n×m网格中，从起点(xs, ys)到终点(xt, yt)
• 每次只能上下左右移动 1 步，不能走障碍物*
• 求最少移动次数，无法到达输出-1

这类题的最优解法是广度优先搜索（BFS），因为 BFS 天然适合求无权图的最短路径。

分析1：为什么不用nextInt() 直接读取m,n?

用

int a = sc.nextInt();
int b = sc.nextInt();

也行，但这道题后面要读一整行地图，混用 nextInt() 和 nextLine() 会吞回车、读空行报错！

Scanner scan = new Scanner(System.in);
String[] nm = scan.nextLine().split(" ");
int n = Integer.valueOf(nm[0].trim());
int m = Integer.valueOf(nm[1].trim());
String[] se = scan.nextLine().split(" ");
// 注意：题目坐标是1-based，代码中转为0-based索引
int xs = Integer.valueOf(se[0].trim()) - 1;
int ys = Integer.valueOf(se[1].trim()) - 1;
int xe = Integer.valueOf(se[2].trim()) - 1;
int ye = Integer.valueOf(se[3].trim()) - 1;

// 读取网格地图
char[][] matrix = new char[n][m];
for (int i = 0; i < n; i++) {
    char[] chrs = scan.nextLine().toCharArray();
    for (int j = 0; j < chrs.length; j++) {
        matrix[i][j] = chrs[j];
    }
}

.split(" ")是按空格切开，变成一堆小字符串，放进字符串数组

.trim()是去掉字符串前后多余空格，防止输入多空格报错。

--创建字符串数组，split()转化为变量的方式读取单个数据

--读取每行数据，循环储存在数组里的方式读取二维数组

分析2:

// 特殊情况：起点就是终点，直接返回0
if (xs == xe && ys == ye) {
    System.out.println(0);
    return;
}

// steps数组：记录每个格子到起点的最短步数，初始为0
int[][] steps = new int[n][m];
steps[xs][ys] = 0;

// 队列用于BFS，存储待遍历的坐标
Queue<int[]> queue = new LinkedList<>();
int[] tmp = new int[] {xs, ys};
queue.add(tmp);