有基础班_day09课上题目
2025-07-09 16:04:07
发布于：上海
6阅读
0回复
0点赞
| 题目 |
|---|
| 【广度优先搜索(三)】二进制矩阵中的最短路径 |
| 【广度优先搜索(三)】观星 |
| 【广度优先搜索(三)】求细胞数量 |
| 【广度优先搜索(三)】打开转盘锁 |
【广度优先搜索(三)】二进制矩阵中的最短路径
题目描述
给定一个 n x n 的二进制矩阵，其中每个元素为 0 或 1。我们从矩阵的左上角 (0, 0) 出发，尝试找到一条路径到达右下角 (n-1, n-1)。该路径必须满足：
- 路径经过的所有单元格的值是
0。 - 路径中相邻的单元格必须是上下左右或对角线方向相连。
- 如果路径存在，返回最短路径的长度；如果没有路径，返回
-1。
输入格式
- 第一行输入一个整数
n，表示矩阵的维度n x n。 - 接下来输入
n行，每行包含n个数字，其中每个数字是0或1，表示该位置是否可以走通。
输出格式
- 输出一个整数，表示从左上角到右下角的最短路径长度。如果没有路径，输出
-1。
解题思路
这是一个典型的最短路径问题，可以使用 广度优先搜索 (BFS) 来解决，因为 BFS 可以找到无权图中从起点到终点的最短路径。
关键步骤：
- BFS遍历：使用队列从
(0, 0)开始遍历，沿着可能的路径逐步扩展，记录每个位置的最短距离。 - 边界条件：如果遇到障碍物（
1）或者超出了矩阵范围，则跳过该位置。 - 八个方向：由于可以在上下左右及四个对角线方向上移动，使用八个方向数组来控制遍历。
- 终止条件：一旦到达右下角
(n-1, n-1)，即返回该位置的最短路径长度。如果 BFS 结束后仍未到达，返回-1。
代码实现
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_N = 100;
int n;
int grid[MAX_N][MAX_N]; // 存储迷宫的矩阵
int dist[MAX_N][MAX_N]; // 存储到每个位置的最短路径长度
// 八个方向的偏移量（上下左右和四个对角线）
int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, -1, 1, 1};
// BFS算法，返回最短路径长度
int bfs() {
queue<pair<int, int>> q; // 队列存储当前位置
q.push({0, 0}); // 从起点(0, 0)开始
dist[0][0] = 1; // 起点的路径长度为1
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
// 如果到达终点，返回路径长度
if (x == n - 1 && y == n - 1) {
return dist[x][y];
}
// 遍历8个方向
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
// 判断新位置是否合法
if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0 && dist[nx][ny] == 0) {
dist[nx][ny] = dist[x][y] + 1; // 更新路径长度
q.push({nx, ny}); // 将新位置加入队列
}
}
}
// 如果无法到达终点，返回-1
return -1;
}
int main() {
cin >> n;
// 输入迷宫矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
}
}
// 如果起点或终点是障碍物，直接返回-1
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
cout << -1 << endl;
return 0;
}
// 初始化dist数组，所有位置初始化为0（表示未访问）
memset(dist, 0, sizeof(dist));
// 调用BFS算法，计算最短路径
cout << bfs() << endl;
return 0;
}
【广度优先搜索(三)】观星
题目描述
给定一个长方形的星空网格，网格中有星星（用 * 表示）和空白区域（用 . 表示）。相邻的星星（包括对角线方向上的相邻）视为同一个星座。我们需要计算星空中有多少个星座，并且输出最大星座的大小（即最大星系包含的星星数量）。
解题思路
这个问题可以通过广度优先搜索（BFS）或者深度优先搜索（DFS）来解决，目的是找到所有相邻的星星并将它们标记为同一个星座。
- BFS/DFS遍历：从每个未访问的星星开始，遍历与它相连的星星，并标记它们为已访问。每次遍历一个新的星星时，都会形成一个新的星座。
- 方向数组：我们可以使用一个方向数组来帮助我们实现8个方向的移动，包括上下左右和4个对角线方向。
- 统计星座大小：每次找到一个新的星座时，记录下该星座的大小，并统计星座的数量。
- 最大星座：更新并记录最大星座的大小。
步骤
- 输入矩阵：首先读取一个
N x M的矩阵，表示星空。 - BFS/DFS：从每个未访问的星星开始，使用 BFS 或 DFS 遍历与它相连的所有星星，计算该星座的大小。
- 统计：统计所有星座的大小，并更新最大星座的大小。
- 输出结果：输出星座的数量和最大星座的大小。
代码实现
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt = 0, ans = 0;
char a[1510][1510]; // 用来存星空
int book[1510][1510]; // 用来标记那些星星我们已经找过他的星座了
int Stars[100010]; // 统计大小为i的星座有多少个
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1}; // 八个方向：上下左右及四个对角线方向
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
struct node {
int x, y; // BFS的结构体，所在第几行，第几列
};
// BFS算法，返回星座大小
int bfs(int p0, int q0) {
queue<node> q;
q.push({p0, q0});
book[p0][q0] = 1;
int Size_ = 0; // 统计星座的大小
while (!q.empty()) {
Size_++;
node temp = q.front();
q.pop();
// 检查八个方向的邻居
for (int i = 0; i < 8; i++) {
int fx = temp.x + dx[i];
int fy = temp.y + dy[i];
// 检查是否越界且是星星且未访问过
if (fx >= 1 && fx <= n && fy >= 1 && fy <= m && a[fx][fy] == '*' && !book[fx][fy]) {
book[fx][fy] = 1;
q.push({fx, fy});
}
}
}
return Size_;
}
int main() {
cin >> n >> m;
// 输入星空矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
int w;
// 遍历所有位置，寻找未访问的星星并计算星座大小
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == '*' && !book[i][j]) {
w = bfs(i, j); // 找到一个新星座，计算其大小
Stars[w]++; // 增加该大小星座的数量
}
}
}
// 统计星系的数量和最大星系的大小
for (int i = 1; i <= 100000; i++) {
if (Stars[i] != 0) {
cnt++;
ans = max(ans, i * Stars[i]); // 更新最大星系的大小
}
}
// 输出星系的数量和最大星系的大小
cout << cnt << " " << ans << endl;
return 0;
}
【广度优先搜索(三)】求细胞数量
题目描述
在一个由数字 0 到 9 构成的矩阵中，数字 1 到 9 代表不同的细胞。细胞是通过上下左右方向连接的数字相邻区域的组合，要求求出矩阵中细胞的个数。
解题思路
这个问题可以通过广度优先搜索（BFS）或者深度优先搜索（DFS）来解决。每个细胞都是由相邻的数字 1-9 组成的区域，我们需要找到这些区域，并统计区域的个数。由于每个细胞的数字值都可能是 1-9，我们需要分别处理每个区域，判断其是否属于同一细胞。
步骤
- 读取输入：首先读取矩阵的大小和矩阵本身。
- 构建地图：用二维数组
Map来存储矩阵信息。每个位置的值是true（表示细胞）或者false（表示空白）。 - 遍历矩阵：使用 BFS 或 DFS 来遍历每个未访问过的细胞，统计每个细胞区域的个数。
- BFS/DFS 实现：对于每个未访问的细胞，启动 BFS 或 DFS，从该细胞开始遍历所有与其相邻的细胞，并将它们标记为已访问，防止重复计数。
- 输出结果：最终输出细胞的数量。
代码实现
#include <bits/stdc++.h>
using namespace std;
struct node {
int x, y;
};
// 定义地图储存数组和标记是否用过数组
bool Map[200][200], p[200][200];
int n, m, ans;
// 数组储存四个方向（上下左右）
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
// 广度优先搜索
void bfs(int x, int y) {
ans++; // 每找到一个新的细胞区域，细胞数量加一
queue<node> q;
q.push({x, y});
while (!q.empty()) {
node now = q.front();
q.pop();
Map[now.x][now.y] = 0; // 将当前细胞标记为已访问
// 扩展到四个方向
for (int i = 0; i < 4; i++) {
int tx = now.x + dx[i];
int ty = now.y + dy[i];
// 判断是否越界，且是细胞
if (tx >= 1 && tx <= m && ty >= 1 && ty <= n && Map[tx][ty]) {
q.push({tx, ty}); // 将相邻的细胞加入队列
Map[tx][ty] = 0; // 标记为已访问
}
}
}
}
int main() {
cin >> m >> n; // 输入矩阵的大小
// 读取矩阵并初始化地图
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char ch;
cin >> ch;
if (ch != '0') {
Map[i][j] = true; // 如果是非零数字，则是细胞
} else {
Map[i][j] = false; // 0 代表空白，不是细胞
}
}
}
// 遍历所有位置，使用 BFS 计算细胞数量
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 如果当前位置没有被访问且是细胞
if (Map[i][j]) {
bfs(i, j); // 从当前位置开始 BFS
}
}
}
// 输出结果：细胞的总数
cout << ans << endl;
return 0;
}
【广度优先搜索(三)】打开转盘锁
题目描述
给定一个四位数字密码锁，密码的每一位都可以进行两种操作：
- 将某一位数字增加 1，如果对 9 操作将会变为 1。
- 将某一位数字减少 1，如果对 1 操作将会变为 9。
我们需要从当前密码到目标密码，求最少的操作次数。
解题思路
本题是典型的 广度优先搜索 (BFS) 应用，BFS 可以有效地求解从起始状态到目标状态的最短路径问题。在这个问题中，每个状态表示一个四位数的密码，每次可以进行两种操作，BFS 通过遍历所有可能的状态，并且寻找从起始状态到目标状态的最短路径。
具体步骤
- 状态表示：将密码的每一位数字表示为一个状态，因此密码是一个包含四个数字的状态
(num[0], num[1], num[2], num[3])。 - 状态转移：每次操作可以选择加一或减一某一位数字，产生一个新的状态。
- 广度优先搜索：从初始状态开始，使用队列保存状态，逐步扩展所有可以到达的状态。当目标状态被找到时，返回当前步数。
BFS 过程
- 初始化：将起始密码状态入队，初始化步数为 0。
- 队列操作：对于队列中的每个状态，尝试通过加一或减一某一位数字来生成新的状态。
- 终止条件：如果当前状态为目标密码，返回当前的步数。
- 已访问标记：使用
vis数组记录已经访问过的状态，避免重复处理。
代码实现
#include <bits/stdc++.h>
using namespace std;
// 定义一个结构体来表示每个状态
struct node {
int num[4]; // 记录四位密码的数字
int step; // 当前状态的步数
} first, last;
// 定义一个 vis 数组，用来标记状态是否访问过
int vis[10][10][10][10];
// 广度优先搜索 (BFS) 算法
int bfs() {
node a, next;
a = first;
a.step = 0;
// 队列用于存储当前状态
queue<node> q;
q.push(a);
// 标记队首元素已经访问
vis[a.num[0]][a.num[1]][a.num[2]][a.num[3]] = 1;
while (!q.empty()) {
a = q.front();
q.pop();
// 终止条件：如果当前状态为目标状态，返回步数
if (a.num[0] == last.num[0] && a.num[1] == last.num[1] && a.num[2] == last.num[2] && a.num[3] == last.num[3]) {
return a.step;
}
// 对每一位数字进行 +1 操作
for (int i = 0; i < 4; i++) {
next = a;
next.num[i]++;
if (next.num[i] == 10) {
next.num[i] = 1; // 如果数字变成 10，则变为 1
}
// 如果未访问过此状态，则入队并标记
if (!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]) {
vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
next.step = a.step + 1;
q.push(next);
}
}
// 对每一位数字进行 -1 操作
for (int i = 0; i < 4; i++) {
next = a;
next.num[i]--;
if (next.num[i] == 0) {
next.num[i] = 9; // 如果数字变成 0，则变为 9
}
// 如果未访问过此状态，则入队并标记
if (!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]) {
vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
next.step = a.step + 1;
q.push(next);
}
}
}
// 如果无法到达目标，返回 -1
return -1;
}
int main() {
// 输入当前密码和目标密码
string start_str, end_str;
cin >> start_str >> end_str;
// 初始化起始状态和目标状态
for (int i = 0; i < 4; i++) {
first.num[i] = start_str[i] - '0';
last.num[i] = end_str[i] - '0';
}
// 调用 BFS 寻找最短路径
int result = bfs();
// 输出结果
cout << result << endl;
return 0;
}
这里空空如也
有帮助，赞一个