有基础班_day07课上题目
2025-07-07 16:32:48
发布于：上海
24阅读
0回复
0点赞
| 题目 |
|---|
| 数水坑 |
| 填涂颜色 |
| 细胞 |
| 南方小土豆 |
| 红与黑 |
数水坑
题目分析
题目给出了一个 的网格，其中每个格子可能是水坑（'W'）或者是旱地（'.'）。我们需要统计网格中有多少个水坑。水坑定义为一组相邻的 'W' 组成的区域，并且相邻的格子可以是上下左右和四个对角线的方向。
解题思路
这是一个经典的图的连通块问题。
- DFS 思路：
- 从网格中的每个 'W' 开始进行深度优先搜索，标记这个水坑区域中的所有 'W' 为已访问（例如，可以将它们改为 '.'），避免重复计数。
- 每发现一个 'W'，就启动一次 DFS 搜索，并增加水坑的计数。
- 通过 DFS 可以在找到一个 'W' 时，递归地探索其相邻的八个格子（上下左右及四个对角线）。
- 边界判断：
- 需要确保 DFS 过程中，每次访问的点都在网格内，避免访问越界。
- 时间复杂度：
- 时间复杂度为 ，每个格子最多被访问一次，DFS 的递归深度与网格大小成正比。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int maxn = 150;
int n, m, water;
char g[maxn][maxn];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 八个方向
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
void dfs(int x, int y) {
g[x][y] = '.'; // 将该位置标记为已访问
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i]; // 计算相邻位置
// 确保新位置在网格内，并且该位置是水坑
if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && g[nx][ny] == 'W') {
dfs(nx, ny);
}
}
}
int main() {
cin >> n >> m;
// 输入网格
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
// 遍历每个格子，查找水坑
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == 'W') { // 找到一个未访问的水坑
dfs(i, j); // 从该点开始进行深度优先搜索
water++; // 增加水坑计数
}
}
}
cout << water << endl; // 输出水坑的数量
return 0;
}
填涂颜色
题目分析
给定一个 的矩阵，其中包含数字 0 和 1，我们需要根据要求将其中的“闭合圈”内部的 0 填充成 2。闭合圈由 1 构成，围住了一部分 0。我们需要找到这些被 1 围住的 0，并将它们填涂为 2。
思路：
- 首先，需要找到矩阵边缘的
0，这些0是与外部空地连接的，应该保持不变。通过深度优先搜索（DFS）或广度优先搜索（BFS）可以标记所有与边缘相连的0。 - 接下来，将剩余的
0视为被围住的0，将这些0填充为2。
解题步骤
- 遍历矩阵边缘：从矩阵的边缘开始，找到所有与边缘连接的
0，并用 DFS 将它们标记为已访问。 - 处理内部
0：对于没有被标记的0，它们就被1围住，应该填涂为2。 - 输出最终矩阵：将矩阵按照填涂规则输出。
关键点
- DFS 递归：通过 DFS 从矩阵边缘开始递归遍历所有与边缘连接的
0。 - 时间复杂度：由于每个节点最多被访问一次，DFS 的时间复杂度为 ，适用于最大矩阵尺寸 。
代码实现
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 50;
int n, g[maxn][maxn];
int dx[] = {1, -1, 0, 0}; // 4个方向的移动
int dy[] = {0, 0, 1, -1}; // 4个方向的移动
// DFS搜索所有与边缘相连的0
void dfs(int x, int y) {
g[x][y] = -1; // 将找到的0变成-1，表示已访问
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i]; // 计算新位置
// 确保在范围内并且是未访问的0
if (nx >= 0 && ny >= 0 && nx < n && ny < n && g[nx][ny] == 0) {
dfs(nx, ny);
}
}
}
int main() {
cin >> n;
// 输入矩阵
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> g[i][j];
// 从矩阵的边缘开始DFS标记与边缘相连的0
for (int i = 0; i < n; i++) {
if (g[i][0] == 0) dfs(i, 0); // 左边缘
if (g[i][n-1] == 0) dfs(i, n-1); // 右边缘
}
for (int j = 0; j < n; j++) {
if (g[0][j] == 0) dfs(0, j); // 上边缘
if (g[n-1][j] == 0) dfs(n-1, j); // 下边缘
}
// 填涂区域：将未被标记的0填涂为2
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 0) {
g[i][j] = 2; // 被1围住的0，填涂为2
}
else if(g[i][j] == -1) {
g[i][j] = 0; // 把被标记的0改回0
}
}
}
// 输出结果
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << g[i][j] << " ";
}
cout << endl;
}
return 0;
}
细胞
题目描述
给定一个矩形阵列，其中每个位置有一个数字 0 到 9，其中 1 到 9 代表细胞。细胞是指在矩阵中，沿着上下左右相连的细胞数字形成的区域。我们需要求出该矩阵中细胞的个数。
输入格式
- 第一行输入两个整数
n和m，分别表示矩阵的行数和列数。 - 接下来有
n行，每行有m个数字，表示矩阵的每个元素。
输出格式
- 输出一个整数，表示矩阵中的细胞个数。
思路分析
1. 问题本质
- 本题是一个典型的 联通区域计数问题，与“岛屿问题”类似。每个细胞由一个数字的区域组成，且细胞之间相连的条件是上下左右相邻且数字相同。
- 我们可以使用 DFS（深度优先搜索） 或 BFS（广度优先搜索） 来遍历每一个细胞，找到每一个连通的细胞区域，并统计数量。
2. 解题步骤
- 构造矩阵：根据输入构造一个
n x m的矩阵，标记每个位置的值。 - DFS 遍历：我们可以用 DFS 从一个细胞数字（数字
1到9）开始，递归遍历该细胞区域内的所有相邻细胞，标记已访问的细胞，避免重复计算。 - 计数细胞：每次遇到一个未访问的细胞时，执行一次 DFS，计数细胞数量。
3. 细节
- 确保处理矩阵的边界，防止访问越界。
- 需要维护一个访问标记，避免重复访问已遍历的细胞。
算法实现
- DFS 搜索：从每个未访问的细胞出发，递归标记所有相邻的同一细胞区域。
- 时间复杂度：每个细胞最多被访问一次，DFS 的时间复杂度为 ，适合本题的输入限制。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 50; // 最大矩阵大小
int n, m; // 行数和列数
char g[maxn][maxn]; // 存储矩阵
int dx[] = {-1, 1, 0, 0}; // 上下左右的移动方向
int dy[] = {0, 0, 1, -1}; // 上下左右的移动方向
// DFS函数，用于标记与当前细胞相连的所有细胞
void dfs(int x, int y) {
g[x][y] = '0'; // 将当前细胞标记为已访问
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i]; // 计算新位置
// 确保在范围内且是未访问的细胞
if (nx >= 0 && ny >= 0 && nx < n && ny < m && g[nx][ny] != '0') {
dfs(nx, ny); // 递归访问
}
}
}
int main() {
cin >> n >> m; // 输入矩阵大小
// 输入矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j]; // 读取每个元素
}
}
int cnt = 0; // 细胞数量
// 遍历整个矩阵，进行 DFS 搜索
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] != '0') { // 找到未访问的细胞
dfs(i, j); // 进行 DFS
cnt++; // 细胞数量加1
}
}
}
cout << cnt << endl; // 输出细胞数量
return 0;
}
南方小土豆
题目描述
给定一个 N x M 的矩阵，每个位置的数字代表一种农作物（1 到 9）。数字相同的农作物在矩阵中如果相连，则视为同一块。要求计算每种农作物有多少块连通区域。区域是上下左右相邻的相同数字构成的。
输入格式
- 第一行输入两个整数
N和M，分别表示矩阵的行数和列数。 - 接下来的
N行，每行包含M个数字，表示每个网格的内容。
输出格式
输出一行，包含 9 个整数，每个整数代表对应农作物的块数（从 1 到 9）。
思路分析
1. DFS/DFS 搜索
- 题目本质是图的联通块计数问题。每一块农作物可以看作是一个连通的区域，矩阵中相同数字的上下左右相邻部分是同一块农作物。
- 我们可以使用 深度优先搜索（DFS） 来遍历这些区域。通过遍历每一个未访问过的细胞，将其标记为已访问，并递归地遍历其四个方向的相邻细胞，直到所有相连的区域都被标记。
2. 步骤
- 构建矩阵：根据输入数据构建矩阵。
- DFS 遍历：从每一个未访问过的农作物开始执行 DFS，标记并统计每块农作物区域。
- 输出结果：最后输出每种农作物的块数。
3. 注意点
- DFS 中需要确保不越界，且只有当该位置的数字和当前农作物相同且未访问时，才继续递归。
- 通过二维数组来存储每个位置的访问状态，避免重复访问。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 9; // 最大矩阵大小
char mp[maxn][maxn]; // 存储矩阵
bool vis[maxn][maxn]; // 访问标记数组
int n, m; // 行数和列数
int num[13]; // 存储每种农作物的块数（索引从1到9）
// 定义四个方向：上下左右
int to[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 深度优先搜索
void dfs(int x, int y, char ch) {
vis[x][y] = true; // 标记当前节点已访问
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int tx = x + to[i][0], ty = y + to[i][1];
// 确保在矩阵内，且是相同的农作物，且未访问
if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && mp[tx][ty] == ch) {
dfs(tx, ty, ch); // 递归
}
}
}
int main() {
cin >> n >> m; // 输入矩阵的行数和列数
for (int i = 0; i < n; i++) {
cin >> mp[i]; // 输入每一行的农作物数据
}
// 遍历每一个细胞
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果当前细胞没有被访问过
if (!vis[i][j]) {
int id = mp[i][j] - '0'; // 获取当前农作物编号
num[id]++; // 该农作物块数加1
dfs(i, j, mp[i][j]); // 从该细胞开始进行深度优先搜索
}
}
}
// 输出每种农作物的块数，注意从1到9
for (int i = 1; i <= 9; i++) {
cout << num[i] << " ";
}
cout << endl;
return 0;
}
红与黑
题目描述
给定一个长方形的房间，地面上铺有红色（'R'）和黑色（'B'）的瓷砖，你从一个特殊的黑色瓷砖（'@'）出发，要求计算你能够到达多少块黑色瓷砖。你只能在相邻的黑色瓷砖之间移动。相邻是指上下左右四个方向。
输入格式
- 第一行输入两个整数
n和m，表示房间的行数和列数。 - 接下来是
n行，每行m个字符，表示房间的瓷砖颜色，其中：'B'表示黑色瓷砖。'R'表示红色瓷砖。'@'表示黑色瓷砖，并且你站在这块瓷砖上，且唯一出现一次。
输出格式
输出一个整数，表示你从初始位置出发能够到达的黑色瓷砖数（包括起始瓷砖）。
思路分析
这题的核心是图的连通性问题。可以将问题建模为一个矩阵，求出从起始位置 '@' 开始，通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历所有相连的黑色瓷砖的数量。
1. DFS 遍历
- 我们可以使用 深度优先搜索（DFS） 来遍历从起始位置
'@'出发，能够到达的所有相连的黑色瓷砖。 - 通过递归的方式，探索每个相邻的黑色瓷砖，直到所有可以到达的瓷砖都被访问。
2. 步骤
- 输入矩阵：根据输入数据构建矩阵，找到起始位置
'@'。 - DFS 遍历：从起始位置出发，递归地访问所有与其相连的黑色瓷砖。
- 输出结果：最终输出能够到达的黑色瓷砖数量。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int maxn = 29; // 最大的矩阵大小
int n, m, sum;
char mp[maxn][maxn]; // 存储房间的矩阵
bool vis[maxn][maxn]; // 访问标记数组
// 定义四个方向：上下左右
int to[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 深度优先搜索
void dfs(int x, int y) {
vis[x][y] = true; // 标记当前节点已访问
sum++;
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int tx = x + to[i][0], ty = y + to[i][1];
// 确保在矩阵内，且是黑色瓷砖，且未访问过
if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && mp[tx][ty] == 'B') {
dfs(tx, ty); // 递归访问
}
}
}
int main() {
cin >> n >> m; // 输入矩阵的行数和列数
// 输入矩阵，找起始点的位置
int bx, by;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mp[i][j];
if (mp[i][j] == '@') {
bx = i;
by = j;
}
}
}
// 从起始位置开始进行深度优先搜索
sum = 0;
dfs(bx, by);
// 输出结果，能够到达的黑色瓷砖数量
cout << sum << endl;
return 0;
}
全部评论 1
#include <bits/stdc++.h> using namespace std; const int maxn = 29; // 最大的矩阵大小 int n, m, sum; char mp[maxn][maxn]; // 存储房间的矩阵 bool vis[maxn][maxn]; // 访问标记数组 // 定义四个方向：上下左右 int to[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 深度优先搜索 void dfs(int x, int y) { vis[x][y] = true; // 标记当前节点已访问 sum++; // 遍历四个方向 for (int i = 0; i < 4; i++) { int tx = x + to[i][0], ty = y + to[i][1]; // 确保在矩阵内，且是黑色瓷砖，且未访问过 if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && mp[tx][ty] == 'B') { dfs(tx, ty); // 递归访问 } } } int main() { cin >> n >> m; // 输入矩阵的行数和列数 // 输入矩阵，找起始点的位置 int bx, by; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> mp[i][j]; if (mp[i][j] == '@') { bx = i; by = j; } } } // 从起始位置开始进行深度优先搜索 sum = 0; dfs(bx, by); // 输出结果，能够到达的黑色瓷砖数量 cout << sum << endl; return 0; }2025-07-09 来自 加拿大
0
有帮助，赞一个