2025寒假算法练习——Week 8
文章目录
前段时间做的搜索练习题
习题均来自 NEFU OJ
Problem 784 | 白与黑-搜索
- Description
有一间长方形的房子，地上铺了白色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
- Input
包括多个数据集合。每个数据集合的第一行是两个整数W 和H，分别表示x 方向
和y 方向瓷砖的数量。W 和H 都不超过20。在接下来的H 行中，每行包括W 个字符。
每个字符表示一块瓷砖的颜色，规则如下：
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
- Output
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
- Sample Input
16 9
2....#.
3.....#
4......
5......
6......
7......
8......
9#@...#
10.#..#.
110 0
- Sample Output
145
广搜找连通块。
1import java.util.Scanner;
2import java.util.Queue;
3import java.util.LinkedList;
4
5public class Main {
6 public static void main(String[] args) {
7 int[] directions = { 1, 0, -1, 0, 0, 1, 0, -1 };
8 try (Scanner sc = new Scanner(System.in)) {
9 while (true) {
10 int col = sc.nextInt(), row = sc.nextInt();
11 if (col == 0 && row == 0) {
12 break;
13 }
14 sc.nextLine();
15 Boolean[][] tiles = new Boolean[row][col];
16 int x = 0, y = 0;
17 for (int i = 0; i < row; i++) {
18 String line = sc.nextLine();
19 for (int j = 0; j < col; j++) {
20 tiles[i][j] = line.charAt(j) == '#' ? false : true;
21 if (line.charAt(j) == '@') {
22 x = i;
23 y = j;
24 }
25 }
26 }
27
28 Queue<int[]> queue = new LinkedList<>();
29 int count = 0;
30 queue.add(new int[] { x, y });
31 tiles[x][y] = false;
32 while (!queue.isEmpty()) {
33 int[] curr = queue.poll();
34 count++;
35 for (int i = 0; i < 8; i += 2) {
36 int nx = curr[0] + directions[i], ny = curr[1] + directions[i + 1];
37 if (nx >= 0 && nx < row && ny >= 0 && ny < col && tiles[nx][ny]) {
38 queue.offer(new int[] { nx, ny });
39 tiles[nx][ny] = false;
40 }
41 }
42 }
43 System.out.println(count);
44 }
45 }
46 }
47}
Problem 558 | 迷宫寻路-搜索
- Description
AC小公主很喜欢设计迷宫，她设计的迷宫只有两个口，一个入口，一个出口。但小公主有时候很调皮，她会让挑战者走不出迷宫。现在给你AC小公主的迷宫请你判断挑战者能否成功从出口走出迷宫，迷宫包证边界为障碍物，只有两个不同的入口。
“#”代表障碍物，“*”代表可走的路。
- Input
输入有多组，每组输入两个正整数n，m（ 2 < n < m < 1000）。
接下来n行，每行有m个字符。
- Output
每组测试实例，若挑战者能走出迷宫输出”YES”，否则输出“NO”。
- Sample Input
13 3
2#*#
3#*#
4#*#
53 3
6#*#
7###
8#*#
- Sample Output
1YES
2NO
这道题用深搜和广搜都能解。
广搜写法：
1import java.util.Scanner;
2import java.util.Queue;
3import java.util.LinkedList;
4
5public class Main {
6 public static void main(String[] args) {
7 int[] directions = { 1, 0, -1, 0, 0, 1, 0, -1 };
8 try (Scanner sc = new Scanner(System.in)) {
9 while (sc.hasNext()) {
10 int row = sc.nextInt(), col = sc.nextInt();
11 Boolean[][] maze = new Boolean[row][col];
12 String line;
13 int x = 0, y = 0;
14 for (int i = 0; i < row; i++) {
15 line = sc.next();
16 for (int j = 0; j < col; j++) {
17 maze[i][j] = line.charAt(j) == '*';
18 if ((i == 0 || i == row - 1 || j == 0 || j == col - 1) && maze[i][j]) {
19 x = i;
20 y = j;
21 }
22 }
23 }
24
25 boolean found = false;
26 Queue<int[]> queue = new LinkedList<>();
27 queue.add(new int[] { x, y });
28 maze[x][y] = false;
29 while (!queue.isEmpty()) {
30 int[] curr = queue.poll();
31 if ((curr[0] == 0 || curr[0] == row - 1 || curr[1] == 0 || curr[1] == col - 1)
32 && !(curr[0] == x && curr[1] == y)) {
33 System.out.println("YES");
34 found = true;
35 break;
36 }
37 for (int i = 0; i < 8; i += 2) {
38 int nx = curr[0] + directions[i], ny = curr[1] + directions[i + 1];
39 if (nx >= 0 && nx < row && ny >= 0 && ny < col && maze[nx][ny]) {
40 maze[nx][ny] = false;
41 queue.add(new int[] { nx, ny });
42 }
43 }
44 }
45 if (!found) {
46 System.out.println("NO");
47 }
48 }
49 }
50 }
51}
深搜写法：
1import java.util.Scanner;
2
3public class Main {
4
5 public static int[] directions = { 1, 0, -1, 0, 0, 1, 0, -1 };
6
7 public static void main(String[] args) {
8 try (Scanner sc = new Scanner(System.in)) {
9 while (sc.hasNext()) {
10 int row = sc.nextInt(), col = sc.nextInt();
11 Boolean[][] maze = new Boolean[row][col];
12 String line;
13 int beginX = 0, beginY = 0, endX = 0, endY = 0;
14 for (int i = 0; i < row; i++) {
15 line = sc.next();
16 for (int j = 0; j < col; j++) {
17 maze[i][j] = line.charAt(j) == '*';
18 if ((i == 0 || i == row - 1 || j == 0 || j == col - 1) && maze[i][j]) {
19 if (beginX == 0 && beginY == 0) {
20 beginX = i;
21 beginY = j;
22 } else {
23 endX = i;
24 endY = j;
25 }
26 }
27 }
28 }
29
30 if (dfs(maze, beginX, beginY, endX, endY, row, col)) {
31 System.out.println("YES");
32 } else {
33 System.out.println("NO");
34 }
35 }
36 }
37 }
38
39 public static boolean dfs(Boolean[][] maze, int x, int y, int endX, int endY, int row, int col) {
40 maze[x][y] = false;
41 if (x == endX && y == endY) {
42 return true;
43 }
44
45 boolean result = false;
46 for (int i = 0; i < 8; i += 2) {
47 int nextX = x + directions[i];
48 int nextY = y + directions[i + 1];
49 if (nextX >= 0 && nextX < row && nextY >= 0 && nextY < col && maze[nextX][nextY]) {
50 result = dfs(maze, nextX, nextY, endX, endY, row, col) || result;
51 }
52 }
53
54 return result;
55 }
56}
maze 数组既可以用来记录路径，又可以当作 visited 用。
Problem 1696 | 猴群-搜索
- Description
给你一个数字矩阵，其中数字由0-9构成，0代表树木，1-9代表猴子；凡是有0和边缘围起来的区域是猴群。请你计算猴群的数目？
- Input
第1行为n和 m，代表行和列数，（1<=n,m<=100）
- Output
输出猴群的数目！
- Sample Input
14 10
20234500067
31034560500
42045600671
50000000089
- Sample Output
14
1import java.util.Scanner;
2import java.util.Queue;
3import java.util.LinkedList;
4
5public class Main {
6
7 public static void main(String[] args) {
8 int[] directioins = { 1, 0, -1, 0, 0, 1, 0, -1 };
9 try (Scanner sc = new Scanner(System.in)) {
10 int row = sc.nextInt(), col = sc.nextInt();
11 sc.nextLine();
12 int[][] forest = new int[row][col];
13 String line;
14 for (int i = 0; i < row; i++) {
15 line = sc.nextLine();
16 for (int j = 0; j < col; j++) {
17 forest[i][j] = line.charAt(j) == '0' ? 0 : 1;
18 }
19 }
20
21 int count = 0;
22 for (int i = 0; i < row; i++) {
23 for (int j = 0; j < col; j++) {
24 if (forest[i][j] != 0) {
25 Queue<int[]> queue = new LinkedList<>();
26 queue.add(new int[] { i, j });
27 forest[i][j] = 0;
28 while (!queue.isEmpty()) {
29 int[] curr = queue.poll();
30 for (int k = 0; k < 8; k += 2) {
31 int x = curr[0] + directioins[k], y = curr[1] + directioins[k + 1];
32 if (x >= 0 && x < row && y >= 0 && y < col && forest[x][y] != 0) {
33 queue.add(new int[] { x, y });
34 forest[x][y] = 0;
35 }
36 }
37 }
38 count++;
39 }
40 }
41 }
42
43 System.out.println(count);
44 }
45 }
46}
Problem 1702 | 01迷宫-搜索
- Description
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
- Input
第1行为两个正整数n,m.
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。
- Output
m行，对于每个询问输出相应答案。
- Sample Input
12 2
201
310
41 1
52 2
- Sample Output
14
24
- Hint
n<=1000,m<=100000
- Source
洛谷 2020.1.27，数据已更新，原题解可能超时
又是一个找连通块问题。为了避免超时，首先要用 C++ 做（Java 确实会超时），其次不要一上来就把所有连通块都搜索一遍。每次查询时先看看这一个连通块之前是不是处理过，如果处理过就直接输出，否则再搜索，而且每次搜索完都将结果存起来。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <queue>
5
6using namespace std;
7
8int directions[8] = { 1, 0, -1, 0, 0, 1, 0, -1 };
9char line[1005];
10bool maze[1005][1005];
11bool visited[1005][1005] = { false };
12int memo[1005][1005] = { 0 };
13
14void bfs(int x, int y, int n) {
15 queue<pair<int, int>> cache;
16 queue<pair<int, int>> q;
17 int count = 0;
18 q.push(make_pair(x, y));
19 visited[x][y] = true;
20 while (!q.empty()) {
21 int cx = q.front().first;
22 int cy = q.front().second;
23 count++;
24 cache.push(q.front());
25 q.pop();
26
27 for (int i = 0; i < 8; i += 2) {
28 int nx = cx + directions[i];
29 int ny = cy + directions[i + 1];
30 if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && maze[nx][ny] ^ maze[cx][cy]) {
31 q.push(make_pair(nx, ny));
32 visited[nx][ny] = true;
33 }
34 }
35 }
36
37 while (!cache.empty()) {
38 int cx = cache.front().first;
39 int cy = cache.front().second;
40 memo[cx][cy] = count;
41 cache.pop();
42 }
43}
44
45int main() {
46 int n, m;
47 scanf("%d %d", &n, &m);
48 for (int i = 0; i < n; i++) {
49 scanf("%s", &line);
50 for (int j = 0; j < n; j++) {
51 maze[i][j] = line[j] == '1';
52 }
53 }
54
55 for (int i = 0; i < m; i++) {
56 int x, y;
57 scanf("%d %d", &x, &y);
58 x--;
59 y--;
60 if (visited[x][y]) {
61 printf("%d\n", memo[x][y]);
62 continue;
63 }
64 else {
65 bfs(x, y, n);
66 printf("%d\n", memo[x][y]);
67 }
68 }
69}