java 洛谷题单【算法1-7】搜索

P1219 [USACO1.5] 八皇后 Checker Challenge

解题思路

回溯法

递归与回溯:

• 从第0行开始，为每个行尝试放置棋子的位置，检查放置是否违反约束条件。
• 如果放置合法，则继续递归处理下一行（即下一层递归）。
• 如果当前行无法找到合法位置，说明之前的摆放有误，需回溯到上一层，重新选择其他位置。

当n=13时代码会超时，这里打表解决。本题也可以直接全部打表。

import java.util.ArrayList;
import java.util.Scanner;public class Main {static int ans = 0;public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();if (n == 13) {System.out.println("1 3 5 2 9 12 10 13 4 6 8 11 7 ");System.out.println("1 3 5 7 9 11 13 2 4 6 8 10 12 ");System.out.println("1 3 5 7 12 10 13 6 4 2 8 11 9 ");System.out.println("73712");return;}solveNQueens(n);System.out.println(ans);}public static void solveNQueens(int n) {// 如果n小于等于0，直接返回if (n <= 0) {return;}// 调用solve方法，解n皇后问题solve(n, new ArrayList<>(), new ArrayList<>());}private static void solve(int n, ArrayList<Integer> row, ArrayList<Integer> col) {// 如果行的长度等于n，则打印结果if (row.size() == n) {print(row);return;}// 遍历每一列for (int i = 0; i < n; i++) {// 如果这一列没有被使用过，且这一行满足条件if (!col.contains(i) && isValid(row, i)) {// 将这一列添加到行中row.add(i);// 将这一列添加到列中col.add(i);// 递归调用solve(n, row, col);// 回溯row.remove(row.size() - 1);col.remove(col.size() - 1);}}}// 判断当前位置是否可以放置皇后private static boolean isValid(ArrayList<Integer> row, int col) {// 遍历已经放置皇后的列for (int i = 0; i < row.size(); i++) {// 判断当前位置的列和已经放置皇后的列是否相等，或者当前位置的列和已经放置皇后的列的绝对值是否等于当前位置的行和已经放置皇后的行的差值if (row.get(i) == col || Math.abs(row.get(i) - col) == row.size() - i) {return false;}}return true;}private static void print(ArrayList<Integer> row) {int n = row.size();// 输出前3种答案if (ans < 3){for (Integer integer : row) {for (int j = 0; j < n; j++) {if (integer == j) {j++;System.out.print(j + " ");}}}System.out.println();}ans++;}
}

DFS

一步到位

import java.util.Scanner;public class Main {static final int N = 14; // 最大棋盘大小，比13大就行static boolean[] col = new boolean[N]; // 记录列是否被占用static boolean[] dia1 = new boolean[2 * N]; // 记录主对角线是否被占用static boolean[] dia2 = new boolean[2 * N]; // 记录副对角线是否被占用static int[] pos = new int[N]; // 存放当前棋子的放置位置static int n, ans = 0; // n 为棋盘大小，ans 为找到的解的数量static void dfs(int u) {if (u > n) { // 如果棋子放置完毕if (ans < 3) { // 如果找到的解少于 3 个for (int i = 1; i <= n; i++) {System.out.print(pos[i] + " ");}System.out.println();}ans++; // 解的数量加 1return;}for (int i = 1; i <= n; i++) {// 检查当前位置是否合法if (col[i] || dia1[u - i + n] || dia2[i + u]) continue;col[i] = true; // 标记列为已被占用dia1[u - i + n] = true; // 标记主对角线为已被占用dia2[i + u] = true; // 标记副对角线为已被占用pos[u] = i; // 放置棋子dfs(u + 1); // 尝试放置下一个棋子// 回溯col[i] = false; // 取消标记列为未被占用dia1[u - i + n] = false; // 取消标记主对角线为未被占用dia2[i + u] = false; // 取消标记副对角线为未被占用pos[u] = 0; // 清空当前位置}}public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();// 从第一行开始放置棋子dfs(1);System.out.println(ans);}
}

P2392 kkksc03考前临时抱佛脚

解题思路

动态规划

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);// 读取每个科目题目的数量int[] a = new int[5];for (int i = 1; i <= 4; i++) {a[i] = input.nextInt();}// 定义用于存储题目时间的数组和动态规划数组int[] homework = new int[21];int[] dp = new int[2501];int totalMinTime = 0;// 对每个科目进行处理for (int i = 1; i <= 4; i++) {int sum = 0;// 读取每个科目的题目时间for (int j = 1; j <= a[i]; j++) {homework[j] = input.nextInt();sum += homework[j];}// 0/1背包算法，计算达到 sum/2 最大时间for (int j = 1; j <= a[i]; j++) {for (int k = sum / 2; k >= homework[j]; k--) {dp[k] = Math.max(dp[k], dp[k - homework[j]] + homework[j]);}}// 累加每个科目达到的最小复习时间totalMinTime += sum - dp[sum / 2];// 重置动态规划数组for (int j = 1; j <= sum / 2; j++) {dp[j] = 0;}}// 输出总最小复习时间System.out.println(totalMinTime);}
}

 搜索

本质上是暴力枚举，遍历每一道题求出左右脑两边时间较大值的最小值，最终返回ans。

import java.util.Scanner;public class Main {// 左脑用时，右脑用时， 最小用时，答案static int Left, Right, min, ans;// 存储问题个数static int[] s = new int[5];// 存储问题和解决时间static int[][] arr = new int[21][5];// x表示当前问题，y表示当前习题集public static void search(int x, int y) {// 如果所有问题都做完了，更新最小用时if (x > s[y]) {min = Math.min(min, Math.max(Left, Right));return;}// 交给左脑做，递归执行，如果符合if判断，得到min值，再回溯，交给右脑做// 找到左右脑两边时间较大值的最小值Left += arr[x][y];search(x + 1, y);Left -= arr[x][y];Right += arr[x][y];search(x + 1, y);Right -= arr[x][y];}public static void main(String[] args) {Scanner input = new Scanner(System.in);for (int i = 0; i < 4; i++) {s[i] = input.nextInt();}// 遍历四个习题集for (int i = 0; i < 4; i++) {Left = Right = 0;min = Integer.MAX_VALUE;// 读入所需时间for (int j = 0; j < s[i]; j++) {arr[j][i] = input.nextInt();}// 开始搜索，从第一个习题集开始，枚举每道题分别给左右脑做，找到最小用时search(0, i);ans += min;}System.out.println(ans);}
}

P1443 马的遍历

解题思路

• 初始化:

  • 创建一个二维数组 dist，用来记录从起始位置 (x, y) 到每个棋盘位置的最少步数。初始化所有位置为 -1（表示不可到达），然后将起始位置的步数设置为 0。
  • 使用一个队列（Queue）来进行 BFS。将起始位置 (x, y) 放入队列中。

• BFS 过程:

  • 从队列中取出当前的位置 (currentX, currentY) 进行处理。
  • 对骑士的 8 种可能的移动方式，计算新的位置 (newX, newY)。
  • 检查新的位置是否在棋盘的范围内，以及是否尚未访问（dist[newX][newY] == -1）。
  • 如果满足条件，则更新 dist 数组中新的位置的步数，并将其加入队列中以备进一步处理。

• 输出结果:

  • 最后，输出棋盘上每个位置的最小步数，如果位置不可达，输出 -1。

import java.util.*;public class Main {// BFSpublic static void minSteps(int n, int m, int x, int y) {// 将起始位置转换为基于0的索引x -= 1;y -= 1;// 象棋中马在棋盘上可能的走法int[][] Moves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},{1, -2}, {1, 2}, {2, -1}, {2, 1}};// 初始化距离矩阵-1(不可达)，并将起始位置的距离设为0int[][] dist = new int[n][m];for (int[] row : dist) {Arrays.fill(row, -1);}dist[x][y] = 0;//BFS队列初始化Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{x, y});// 开始搜索while (!queue.isEmpty()) {int[] current = queue.poll();int currentX = current[0];int currentY = current[1];int currentDist = dist[currentX][currentY];for (int[] move : Moves) {int newX = currentX + move[0];int newY = currentY + move[1];//检查新位置是否在限定范围内并且尚未访问过if (newX >= 0 && newX < n && newY >= 0 && newY < m && dist[newX][newY] == -1) {dist[newX][newY] = currentDist + 1;queue.offer(new int[]{newX, newY});}}}// 输出结果for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {System.out.print(dist[i][j] + " ");}System.out.println();}}public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int m = input.nextInt();int x = input.nextInt();int y = input.nextInt();minSteps(n, m, x, y);}
}

P1135 奇怪的电梯

解题思路

这是一道最短路问题，可以理解为每次建两条边，

DFS深度优先搜索 

import java.util.Arrays;
import java.util.Scanner;public class Main {static int n, a, b;static int[] k = new int[201];// 用于存储从起点到图中所有其他节点的最短距离static int[] dis = new int[201];static void dfs(int node, int step) {dis[node] = step; // 更新距离// 当前层数减去对应的k值，如果大于1并且步数小于当前记录的步数，则继续向下搜索int v = node - k[node];if (1 <= v && step + 1 < dis[v]) {dfs(v, step + 1);}// 当前层数加上对应的k值，如果小于等于n并且步数小于当前记录的步数，则继续向上搜索v = node + k[node];if (v <= n && step + 1 < dis[v]) {dfs(v, step + 1);}}public static void main(String[] args) {Scanner input = new Scanner(System.in);// 初始化距离数组Arrays.fill(dis, Integer.MAX_VALUE);n = input.nextInt();a = input.nextInt();b = input.nextInt();for (int i = 1; i <= n; i++) {k[i] = input.nextInt();}// 从a层开始，目前步数为0dfs(a, 0);// 判断是否能到达b层，不能输出-1，能则输出步数System.out.println(dis[b] == Integer.MAX_VALUE ? -1 : dis[b]);}
}

P2895 [USACO08FEB] Meteor Shower S

解题思路

• 定义问题： 贝茜从起点 (0, 0) 出发，目标是找到一个不会被流星影响的安全格子。由于流星坠落会把坠落点及其四周的格子烧焦，我们需要计算出每个格子变为不可走的最早时间。

• 流星影响范围： 对于每颗流星坠落的位置 (X_i, Y_i)，该流星会将它的周围四个相邻的格子（上下左右四个方向）也烧焦。因此，每颗流星会影响五个格子：(X_i, Y_i) 及其上下左右。

• 最早烧焦时间表： 我们需要一个数组 minBurnTime[x][y] 来记录每个格子最早被烧焦的时刻。初始时，这些值为无穷大（即未被烧焦）。然后，遍历每颗流星，更新流星及其影响的格子的烧焦时间。

• 广度优先搜索 (BFS)： 在时刻 t = 0，贝茜从 (0, 0) 开始，通过 BFS 在四个方向上搜索下一个可以走的格子。我们需要确保贝茜只走在还未被流星烧焦的格子上，并且格子在贝茜抵达的时刻之前没有被烧焦。

• 终止条件： 如果贝茜找到一个永远不会被烧焦的格子，那么返回到达这个格子的最短时间。如果所有可以走的格子最终都被烧焦了，则返回 -1 表示不可能到达安全区域。

import java.util.*;public class Main {// 定义方向向量：上，下，左，右private static final int[] dx = {-1, 1, 0, 0};private static final int[] dy = {0, 0, -1, 1};private static final int MAX_COORD = 305;  // 坐标最大值范围 [0, 300]private static final int INF = Integer.MAX_VALUE;public static void main(String[] args) {Scanner input = new Scanner(System.in);int M = input.nextInt();// 初始化每个格子的最早烧焦时间int[][] minBurnTime = new int[MAX_COORD][MAX_COORD];for (int i = 0; i < MAX_COORD; i++) {Arrays.fill(minBurnTime[i], INF);}// 读取流星信息，并更新烧焦时间for (int i = 0; i < M; i++) {int X = input.nextInt();int Y = input.nextInt();int T = input.nextInt();updateBurnTime(minBurnTime, X, Y, T);}// 用BFS进行最短路径搜索int result = bfs(minBurnTime);System.out.println(result);}// 更新流星影响的格子及其周围格子的烧焦时间private static void updateBurnTime(int[][] minBurnTime, int x, int y, int t) {for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];if (isInBounds(nx, ny)) {minBurnTime[nx][ny] = Math.min(minBurnTime[nx][ny], t);}}minBurnTime[x][y] = Math.min(minBurnTime[x][y], t);  // 流星落地点也要更新}// 广度优先搜索 (BFS) 寻找最短路径private static int bfs(int[][] minBurnTime) {Queue<int[]> queue = new LinkedList<>();boolean[][] visited = new boolean[MAX_COORD][MAX_COORD];queue.offer(new int[]{0, 0, 0});  // {x, y, time}visited[0][0] = true;while (!queue.isEmpty()) {int[] current = queue.poll();int x = current[0];int y = current[1];int time = current[2];// 如果当前位置的烧焦时间大于当前时间，说明贝茜可以安全站在这里if (minBurnTime[x][y] == INF) {return time;  // 找到一个永远不会烧焦的格子}// 遍历四个方向for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];int nextTime = time + 1;if (isInBounds(nx, ny) && !visited[nx][ny] && nextTime < minBurnTime[nx][ny]) {queue.offer(new int[]{nx, ny, nextTime});visited[nx][ny] = true;}}}return -1;  // 无法到达安全地点}// 判断是否在有效范围内private static boolean isInBounds(int x, int y) {return x >= 0 && x < MAX_COORD && y >= 0 && y < MAX_COORD;}
}

P1036 [NOIP2002 普及组] 选数

解题思路

• 组合生成：使用了回溯算法（backtracking）来生成所有可能的组合。generateCombinations 函数递归地构建每一个组合，遇到有效组合时将其加入结果列表。
• 素数判断：isPrime 函数通过检查一个数是否可以被其小于等于平方根的数整除，来判断其是否为素数。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in); int n = input.nextInt(); // 输入数组长度 nint k = input.nextInt(); // 输入要选择的元素个数 kint[] numbers = new int[n]; // 创建长度为 n 的数组用于存放输入的数字for (int i = 0; i < n; i++) {numbers[i] = input.nextInt(); }List<List<Integer>> combinations = new ArrayList<>(); // 用于存放所有 k 个元素的组合// 生成所有长度为 k 的组合generateCombinations(numbers, n, k, 0, new ArrayList<>(), combinations);int primeCount = 0; // 用于计数素数和的组合个数// 遍历所有组合，计算每个组合的元素和，并判断是否为素数for (List<Integer> combination : combinations) {int sum = combination.stream().mapToInt(Integer::intValue).sum(); // 计算组合元素的和if (isPrime(sum)) { // 如果和是素数primeCount++; // 素数组合个数加 1}}System.out.println(primeCount);}// 递归生成数组中长度为 k 的所有组合private static void generateCombinations(int[] arr, int n, int k, int index, List<Integer> current, List<List<Integer>> combinations) {// 如果当前组合的大小等于 k，说明生成了一个合法的组合，加入组合列表if (current.size() == k) {combinations.add(new ArrayList<>(current)); // 保存当前组合return; // 返回不再继续递归}// 如果遍历完了数组，则返回if (index == n) {return;}// 选择当前索引的元素，并继续递归生成剩下的组合current.add(arr[index]);generateCombinations(arr, n, k, index + 1, current, combinations);// 不选择当前索引的元素，尝试其他组合current.remove(current.size() - 1);generateCombinations(arr, n, k, index + 1, current, combinations);}// 判断一个数是否为素数private static boolean isPrime(int num) {if (num <= 1) {return false; // 小于或等于 1 的数不是素数}// 通过检查从 2 到 sqrt(num) 的所有数，判断是否存在能整除 num 的数for (int i = 2; i <= Math.sqrt(num); i++) {if (num % i == 0) { // 如果存在整除因子，说明 num 不是素数return false;}}return true; // 没有发现整除因子，num 是素数}
}

P2036 [COCI2008-2009 #2] PERKET 

解题思路

• 穷举所有可能的配料组合：

  • 这里采用了位运算的技巧来枚举所有可能的食材组合。对于每个食材，可以选择是否加入组合中，因此总共有 2n−12^n - 12n−1 种组合（从 1 到 2n−12^n - 12n−1 表示选择的子集）。
  • i 作为枚举的组合编号，表示当前选择了哪些食材。1 << n 表示有 2n2^n2n 种组合可能（即每个食材可以选择或不选择），从 1 开始，因为编号为 0 的子集是空集。

• 计算酸味和苦味的总值：

  • 对于每一个组合 i，内部循环使用 if ((i & (1 << j)) != 0) 来判断当前组合是否包含第 j 个食材。通过位运算，可以检测到当前组合 i 中是否包含第 j 个食材。
  • 如果包含，就将第 j 个食材的酸味乘入总酸味 totalS，并将苦味加到总苦味 totalB。

• 计算差值并更新最小差值：

  • 对于每个组合，计算总酸味与总苦味之间的绝对差值 currentDifference，并将其与当前最小差值 minDifference 比较。如果当前差值更小，则更新 minDifference。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int[] s = new int[n];int[] b = new int[n];for (int i = 0; i < n; i++) {s[i] = input.nextInt();b[i] = input.nextInt();}int minDifference = Integer.MAX_VALUE;// 枚举所有可能的配料组合（子集）for (int i = 1; i < (1 << n); i++) {int totalS = 1;int totalB = 0;for (int j = 0; j < n; j++) {if ((i & (1 << j)) != 0) {totalS *= s[j];totalB += b[j];}}int currentDifference = Math.abs(totalS - totalB);if (currentDifference < minDifference) {minDifference = currentDifference;}}System.out.println(minDifference);}
}

 P1433 吃奶酪

解题思路

这个问题可以归结为经典的旅行商问题（TSP, Traveling Salesman Problem）。由于小老鼠需要从原点 (0,0) 出发，访问所有的奶酪并返回终点，因此可以使用递归或动态规划的方法来求解最短路径。

• 求距离：根据两点距离公式 $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$ 来计算老鼠从一个点移动到另一个点的距离。
• 递归解决TSP问题：老鼠从原点出发，访问所有奶酪块，然后返回原点。我们可以利用状态压缩动态规划来解决问题，枚举每一个奶酪块作为起点，通过递归计算走遍所有块的最短路径。
• 状态压缩DP：利用一个位掩码来记录已经访问过的奶酪点的状态。

import java.util.Arrays;
import java.util.Scanner;public class Main {static double[][] dist = new double[20][20]; // 距离矩阵，从第i块奶酪到第j块的距离static double[] x = new double[20], y = new double[20]; // 奶酪的坐标static double[][] dp = new double[18][1 << 18]; // 状态压缩DP数组static int n; // 奶酪数量public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();// 读取每块奶酪的坐标for (int i = 1; i <= n; i++) {x[i] = input.nextDouble();y[i] = input.nextDouble();}// 原点 (0, 0)x[0] = 0;y[0] = 0;// 初始化距离矩阵for (int i = 0; i <= n; i++) {for (int j = i + 1; j <= n; j++) {dist[i][j] = distance(i, j);dist[j][i] = dist[i][j]; // 对称性}}// 初始化dp数组，设置为无穷大for (int i = 0; i < 18; i++) {Arrays.fill(dp[i], Double.MAX_VALUE);}// 初始化: 在i点上，且只经过i点时的最短距离为从原点到i点的距离for (int i = 1; i <= n; i++) {dp[i][1 << (i - 1)] = dist[0][i];}// 枚举所有状态for (int mask = 1; mask < (1 << n); mask++) {for (int i = 1; i <= n; i++) {// 如果i点没在当前的状态mask中，跳过if ((mask & (1 << (i - 1))) == 0) continue;// 遍历所有可能的点j，寻找最小值for (int j = 1; j <= n; j++) {if (i == j || (mask & (1 << (j - 1))) == 0) continue;// 更新dp[i][mask]，选择从j到i的最短路径dp[i][mask] = Math.min(dp[i][mask], dp[j][mask ^ (1 << (i - 1))] + dist[i][j]);}}}// 找到走完所有点的最短路径double ans = Double.MAX_VALUE;int finalMask = (1 << n) - 1; // 所有点都经过的状态for (int i = 1; i <= n; i++) {ans = Math.min(ans, dp[i][finalMask]);}// 输出答案，保留两位小数System.out.printf("%.2f\n", ans);}// 计算第v个和第w个奶酪之间的欧几里得距离private static double distance(int v, int w) {return Math.sqrt((x[v] - x[w]) * (x[v] - x[w]) + (y[v] - y[w]) * (y[v] - y[w]));}
}

P1605 迷宫

解题思路

• 使用深度优先搜索（DFS）枚举所有可能的路径。
• 对每一个位置，可以尝试向上、下、左、右四个方向移动。
• 每次移动后需要检查该位置是否为障碍物或已经访问过。
• 如果到达终点则记录方案数。
• 递归回溯过程中注意恢复状态以便探索其他可能路径。

import java.util.Scanner;public class Main {// 迷宫的大小和障碍物位置static int N, M, T;static int[][] maze;// 起点和终点坐标static int startX, startY, endX, endY;// 四个方向数组，用于表示上下左右移动static int[] dx = {0, 1, 0, -1}; // 右、下、左、上static int[] dy = {1, 0, -1, 0}; // 右、下、左、上// 用于记录方案数static int count = 0;// 主函数public static void main(String[] args) {Scanner input = new Scanner(System.in);// 读取迷宫的尺寸和障碍物数目N = input.nextInt();M = input.nextInt();T = input.nextInt();// 初始化迷宫，0 表示可通行，-1 表示障碍物maze = new int[N + 1][M + 1];// 读取起点和终点坐标startX = input.nextInt();startY = input.nextInt();endX = input.nextInt();endY = input.nextInt();// 读取障碍物位置for (int i = 0; i < T; i++) {int obsX = input.nextInt();int obsY = input.nextInt();maze[obsX][obsY] = -1; // 标记障碍物}// 从起点开始深度优先搜索dfs(startX, startY);// 输出结果，即方案的数量System.out.println(count);}// 深度优先搜索函数public static void dfs(int x, int y) {// 如果到达终点，方案数加1if (x == endX && y == endY) {count++;return;}// 将当前点标记为已访问maze[x][y] = 1;// 尝试向四个方向移动for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 检查新位置是否在迷宫范围内，并且是可通行的if (newX >= 1 && newX <= N && newY >= 1 && newY <= M && maze[newX][newY] == 0) {dfs(newX, newY); // 递归进入新位置}}// 回溯：恢复当前点为未访问状态，以便探索其他路径maze[x][y] = 0;}
}

P1019 [NOIP2000 提高组] 单词接龙

解题思路

本题建议参考题解区。本文给出的题解仅供参考。

1. 最小重叠部分计算：

• 首先，定义一个 minOverlap 函数，用于计算两个单词之间的最小重叠部分。具体方法是遍历前一个单词的后缀，寻找是否与下一个单词的前缀有重叠。
• 预处理所有单词对之间的重叠关系，并存储在二维数组 minO[][] 中，表示两个单词之间的最小重叠长度。

2. 深度优先搜索（DFS）：

• 使用深度优先搜索 dfs 进行递归，尝试从以指定字母开头的单词出发，逐个单词接龙。
• 在递归过程中，检查每个单词是否符合连接条件：
  • 单词最多使用两次。
  • 两个单词之间必须有重叠部分。
  • 相邻的两个单词不能存在包含关系。
• 递归过程中，更新当前的接龙长度，并通过回溯的方式还原状态，寻找可能的更长单词链。

3. 回溯和状态更新：

• 每次尝试一个单词连接后，通过回溯的方式撤销选择，以便尝试其他可能的组合。
• 使用 fre[] 数组记录每个单词的使用次数，确保每个单词最多使用两次。

import java.util.Scanner;public class Main {static int n;                   // 单词数static String[] str;             // 存储字符串static int[][] minO;              // 两个单词的最小重叠部分static int[] fre;               // 判断单词使用频率static int ans = -1;            // 答案static int maxL = 0;              // 当前最长串的长度// mt函数，返回x单词后连接一个y单词的最小重叠部分public static int minOverlap(int x, int y) {boolean flag = true;// y单词从尾部向前看看最小重叠部分从哪里开始int ky = 0;int lenX = str[x].length();  // 从y单词的尾部向前看看最小重叠部分从哪里开始// 从x单词的尾部向前看看最小重叠部分从哪里开始for (int k = lenX - 1; k >= 0; k--) {for (int kx = k; kx < lenX; kx++) {// 如果两个单词的字符不相等，则说明不是最小重叠部分if (str[x].charAt(kx) != str[y].charAt(ky++)) {flag = false;break;}}// 如果找到最小重叠部分，则返回重叠部分的长度if (flag) {return lenX - k;}ky = 0;flag = true;}return 0;}// dfs函数，p为尾部单词编号public static void dfs(int p) {boolean flag = false;  // 标记是否能继续连接for (int i = 0; i < n; i++) {if (fre[i] >= 2) continue;               // 单词使用超过两次if (minO[p][i] == 0) continue;             // 两个单词没有重合部分if (minO[p][i] == str[p].length() || minO[p][i] == str[i].length()) continue;  // 存在包含关系maxL += str[i].length() - minO[p][i];         // 更新当前长度fre[i]++;                                // 该单词使用一次flag = true;                               // 标记成功匹配dfs(i);                                  // 递归继续搜索maxL -= str[i].length() - minO[p][i];         // 回溯时减去这部分长度fre[i]--;                                // 回溯时还原使用状态}if (!flag) {  // 如果不能再继续接龙，更新最大值ans = Math.max(ans, maxL);}}public static void main(String[] args) {Scanner input = new Scanner(System.in);// 输入单词数n = input.nextInt();str = new String[n];minO = new int[n][n];fre = new int[n];// 输入单词列表for (int i = 0; i < n; i++) {str[i] = input.next();}// 输入开头的字母char ch = input.next().charAt(0);// 预处理，计算两个单词的最小重叠部分for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {minO[i][j] = minOverlap(i, j);}}// 从每个以开头字母为起点的单词开始搜索for (int i = 0; i < n; i++) {if (str[i].charAt(0) == ch) {fre[i]++;              // 标记该单词使用过maxL = str[i].length();   // 更新当前串长度dfs(i);                // 开始搜索fre[i] = 0;            // 回溯时还原状态}}// 输出结果System.out.println(ans);}
}

P1101 单词方阵

解题思路

• 方向定义：在矩阵中寻找单词时，有 8 个方向需要考虑：上下、左右、四个对角线方向。
• 查找匹配：从每个起始点出发，检查是否可以沿着某个方向找到完整的单词 yizhong。
• 标记匹配：使用一个辅助矩阵来标记哪些字母属于找到的单词，然后根据该标记矩阵输出最终结果。

import java.util.Scanner;public class Main {// 定义8个方向，分别是: 上、下、左、右、左上、右上、左下、右下static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};static String word = "yizhong";  // 要查找的单词static int n;static char[][] matrix; // 输入矩阵static boolean[][] marked;  // 标记矩阵，用于记录找到的单词的位置public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();matrix = new char[n][n];marked = new boolean[n][n];// 读取输入矩阵for (int i = 0; i < n; i++) {matrix[i] = input.next().toCharArray();}// 遍历矩阵的每一个位置for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// 尝试从 (i, j) 位置出发寻找单词for (int d = 0; d < 8; d++) {if (searchWord(i, j, d)) {// 如果找到单词，标记其位置markWord(i, j, d);}}}}// 输出结果printResult();}// 在方向d上查找从 (x, y) 出发的单词是否为 "yizhong"public static boolean searchWord(int x, int y, int d) {for (int k = 0; k < word.length(); k++) {int nx = x + k * dx[d];int ny = y + k * dy[d];if (nx < 0 || nx >= n || ny < 0 || ny >= n || matrix[nx][ny] != word.charAt(k)) {return false;}}return true;}// 标记从 (x, y) 出发，方向d上的单词 "yizhong"public static void markWord(int x, int y, int d) {for (int k = 0; k < word.length(); k++) {int nx = x + k * dx[d];int ny = y + k * dy[d];marked[nx][ny] = true;  // 标记该位置为单词的一部分}}// 输出最终结果，将未标记的字母替换为 '*'public static void printResult() {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (marked[i][j]) {System.out.print(matrix[i][j]);} else {System.out.print('*');}}System.out.println();}}
}

P2404 自然数的拆分问题

解题思路

• 递归与回溯：

  • 我们从最小的数（即 1）开始，不断尝试将剩余的数拆分为更小的数。
  • 使用递归函数来枚举所有可能的拆分方式。
  • 在递归过程中，需要保证当前选择的数字比上一个选择的数字要大或者相等，以保证输出序列是递增的。

• 剪枝：

  • 如果当前的和已经超过了 n，则可以提前终止当前递归分支。
  • 当剩下的数字为 0 时，表示找到了一种可行的拆分方式，将其保存。

• 字典序输出：

  • 因为我们在每次递归时都是从最小的数开始递归，因此自然满足字典序的要求。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {// 用于存储最终结果static List<List<Integer>> result = new ArrayList<>();public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();input.close();// 调用递归方法求解findCombinations(n, new ArrayList<>(), 1);// 按要求格式输出for (List<Integer> combination : result) {for (int i = 0; i < combination.size(); i++) {if (i == combination.size() - 1) {System.out.print(combination.get(i));} else {System.out.print(combination.get(i) + "+");}}System.out.println();}}/*** 递归函数，寻找所有拆分组合* @param target 当前需要拆分的数* @param current 当前组合* @param start 从哪个数开始尝试*/public static void findCombinations(int target, List<Integer> current, int start) {// 如果target为0，表示找到了一种拆分方式if (target == 0) {// 避免保存数字本身这一特例if (current.size() > 1) {result.add(new ArrayList<>(current));}return;}// 从start开始尝试数字，保证组合中的数字递增for (int i = start; i <= target; i++) {current.add(i);findCombinations(target - i, current, i);current.remove(current.size() - 1); // 回溯}}
}

P1596 [USACO10OCT] Lake Counting S

解题思路

• 数据输入与初始化：通过Scanner读取田地的大小N和M，然后输入N行的水坑图，用二维字符数组field存储。我们还用visited二维布尔数组来标记某个位置是否已经访问过。

• 主遍历逻辑：

  • 使用两层循环遍历整个田地的每一个位置，检查是否为水坑('W')且未被访问过。如果满足条件，调用DFS函数进行深度优先搜索，将这个水坑的所有格子都标记为已访问。

• DFS函数：

  • 从当前位置开始，将当前位置标记为已访问，然后尝试向八个方向（上下左右及四个对角线）进行递归搜索。如果新的位置仍在田地范围内且是水坑并且未被访问过，继续递归搜索。

• 输出结果：输出最终统计的水坑数量。

import java.util.Scanner;public class Main {static int n, m;static char[][] field;          // 记录田地的水坑图static boolean[][] visited;     // 记录每个位置是否访问过static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0}; // 上, 左上, 左, 左下, 下, 右下, 右, 右上static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1}; // 对应的y坐标变化public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();m = input.nextInt();field = new char[n][m];visited = new boolean[n][m];// 输入田地的水坑图for (int i = 0; i < n; i++) {field[i] = input.next().toCharArray();}int count = 0; // 记录水坑的数量// 遍历整个田地for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果是水坑，并且没有访问过if (field[i][j] == 'W' && !visited[i][j]) {dfs(i, j); // 使用深度优先搜索标记整个水坑count++; // 水坑数量加1}}}// 输出水坑的数量System.out.println(count);}// 深度优先搜索函数public static void dfs(int x, int y) {visited[x][y] = true; // 标记当前位置已访问// 尝试移动到八个相邻的格子for (int i = 0; i < 8; i++) {int nx = x + dx[i];int ny = y + dy[i];// 判断新位置是否在范围内，并且是水坑且未访问过if (nx >= 0 && nx < n && ny >= 0 && ny < m && field[nx][ny] == 'W' && !visited[nx][ny]) {dfs(nx, ny); // 递归继续访问相邻的水坑格子}}}
}

P1162 填涂颜色

解题思路

• 首先从矩阵的边界出发，使用 DFS 或 BFS 遍历所有与边界连通的 0，将它们标记为外部区域（可以标记为 -1）。
• 遍历矩阵中剩余的 0，这些 0 位于闭合圈内，将它们替换为 2。
• 最后，将标记为 -1 的外部区域恢复为 0，输出最终结果。

import java.util.Scanner;public class Main {static int[][] matrix;    // 定义一个二维数组来存储矩阵static int n;// 定义四个方向static int[] dx = {-1, 1, 0, 0};    static int[] dy = {0, 0, -1, 1};public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();matrix = new int[n][n];// 读入矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = input.nextInt();}}// 从矩阵的边界开始DFS标记外部的0for (int i = 0; i < n; i++) {if (matrix[i][0] == 0) dfs(i, 0); // 左边界if (matrix[i][n - 1] == 0) dfs(i, n - 1); // 右边界}for (int j = 0; j < n; j++) {if (matrix[0][j] == 0) dfs(0, j); // 上边界if (matrix[n - 1][j] == 0) dfs(n - 1, j); // 下边界}// 把剩下的0替换成2，把标记为-1的外部0恢复为0for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {matrix[i][j] = 2; // 闭合圈内的0} else if (matrix[i][j] == -1) {matrix[i][j] = 0; // 外部的0}}}// 输出结果for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(matrix[i][j] + " ");}System.out.println();}}// 使用DFS标记外部的0static void dfs(int x, int y) {matrix[x][y] = -1; // 标记为外部的0for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];// 如果新位置在矩阵范围内且值为0，则继续DFSif (nx >= 0 && nx < n && ny >= 0 && ny < n && matrix[nx][ny] == 0) {dfs(nx, ny);}}}
}

P1032 [NOIP2002 提高组] 字串变换

解题思路

• BFS 初始化：

  • 使用一个队列来存储当前字符串和当前步数的对 (current_string, step_count)。
  • 同时使用一个集合来记录访问过的字符串状态，以避免重复状态的搜索（循环状态）。

• 广度优先搜索：

  • 每次从队列中取出一个字符串状态，检查是否已经变换为了目标字符串B。
  • 对当前字符串应用所有可能的变换规则，生成新的字符串状态并加入队列。
  • 如果应用了某条规则生成的新字符串已经访问过，则跳过。
  • 如果在10步内找到了目标字符串，输出变换的步数。

• 终止条件：

  • 如果队列为空且没有找到目标字符串B，则输出 "NO ANSWER!"。

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取初始字符串和目标字符串String A = scanner.next();String B = scanner.next();// 读取转换规则List<Rule> rules = new ArrayList<>();while (scanner.hasNext()) {String a = scanner.next();String b = scanner.next();rules.add(new Rule(a, b));}// BFS 队列，队列中的每个元素为一个 Pair<当前字符串, 变换步数>Queue<Pair> queue = new LinkedList<>();queue.add(new Pair(A, 0));// 记录访问过的字符串状态，防止重复Set<String> visited = new HashSet<>();visited.add(A);// BFS 遍历while (!queue.isEmpty()) {Pair current = queue.poll();String currentString = current.string;int step = current.step;// 如果当前字符串已经是目标字符串，输出步数并退出if (currentString.equals(B)) {System.out.println(step);return;}// 如果超过10步，则停止搜索if (step >= 10) {continue;}// 对当前字符串尝试所有的转换规则for (Rule rule : rules) {int index = currentString.indexOf(rule.from);while (index != -1) {// 生成新的字符串String newString = currentString.substring(0, index) + rule.to + currentString.substring(index + rule.from.length());// 如果没有访问过这个新字符串状态，则加入队列if (!visited.contains(newString)) {queue.add(new Pair(newString, step + 1));visited.add(newString);}// 继续查找下一个匹配的位置index = currentString.indexOf(rule.from, index + 1);}}}// 如果找不到答案System.out.println("NO ANSWER!");}
}// 辅助类来存储字符串和步数
class Pair {String string;int step;Pair(String s, int step) {this.string = s;this.step = step;}
}// 辅助类来存储变换规则
class Rule {String from;String to;Rule(String from, String to) {this.from = from;this.to = to;}
}

P1825 [USACO11OPEN] Corn Maze S

解题思路

1. 问题分析

• 迷宫中有以下几种元素：
  • # 表示墙壁，无法通过。
  • . 表示空地，可以正常移动。
  • 大写字母 (A-Z) 表示传送门的两端，踏入其中一端会被立即传送到另一端。
  • = 表示出口，我们的目标是从 @ 移动到 =.
  • @ 表示起点，BFS 的起始位置。
• 奶牛只能上下左右四个方向移动，每次移动花费 1 个时间单位。
• 使用传送门从一个端点到另一个端点是瞬间完成的，不花费时间。

2. 解题策略

我们使用广度优先搜索（BFS）来解决这个问题。BFS 的特点是按层遍历，也就是说，当我们第一次到达终点时，一定是花费最少时间的路径。

BFS 的步骤：

1. 初始化：

   • 将起点放入队列，并标记为已访问。
   • 初始化方向数组 d，表示四个可能移动的方向。

2. BFS 遍历：

   • 从队列中取出当前节点，检查是否为终点，如果是终点则返回当前步数。
   • 如果当前节点是传送门（大写字母），则使用 findTeleport 方法找到对应的另一个传送门，将当前位置更新为传送门的另一端。
   • 尝试从当前节点向四个方向移动，如果新位置是空地且未访问过，则将该位置加入队列并标记为已访问。

3. 终止条件：

   • 当队列为空时，即搜索完所有可能的路径，结束搜索。如果此时还没到达终点，则说明没有路径（不过按题意保证有出口）。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int[][] maze = new int[500][500];  // 迷宫表示static boolean[][] visited = new boolean[500][500];  // 访问标记static int n, m;  // 行和列static int sx, sy;  // 起点坐标static int ex, ey;  // 终点坐标static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 方向数组// 存储节点的类static class Node {int x, y, step;Node(int x, int y, int step) {this.x = x;this.y = y;this.step = step;}}public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();m = input.nextInt();input.nextLine();  // 读取换行符char s;for (int i = 1; i <= n; i++) {String line = input.nextLine();for (int j = 1; j <= m; j++) {s = line.charAt(j - 1);if (s == '.') {maze[i][j] = 1;  // 草地可以通过}if (s >= 'A' && s <= 'Z') {maze[i][j] = s;  // 传送门，用字符表示}if (s == '@') {sx = i;sy = j;maze[i][j] = 1;  // 起点}if (s == '=') {ex = i;ey = j;maze[i][j] = 1;  // 终点}}}visited[sx][sy] = true;  // 标记起点为已访问bfs();  // 执行广度优先搜索}// 找到传送门的另一端static void findTeleport(Node node) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 找到与当前传送门字符相同且不是当前位置的传送门if ((i != node.x || j != node.y) && maze[i][j] == maze[node.x][node.y]) {node.x = i;node.y = j;return;}}}}// 广度优先搜索static void bfs() {Queue<Node> queue = new LinkedList<>();queue.add(new Node(sx, sy, 0));  // 起点入队while (!queue.isEmpty()) {Node current = queue.poll();// 如果到达了终点if (current.x == ex && current.y == ey) {System.out.println(current.step);return;}// 如果当前位置是传送门if (maze[current.x][current.y] >= 'A' && maze[current.x][current.y] <= 'Z') {findTeleport(current);  // 找到传送门的另一端}// 尝试四个方向的移动for (int i = 0; i < 4; i++) {int nx = current.x + d[i][0];int ny = current.y + d[i][1];if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && maze[nx][ny] != 0 && !visited[nx][ny]) {visited[nx][ny] = true;  // 标记为已访问queue.add(new Node(nx, ny, current.step + 1));  // 新节点入队，步数加 1}}}}
}