U5-3-DFS3
原题链接：67324.4.0U5笔记合集
2025-08-31 11:24:38
发布于：江苏
10阅读
0回复
0点赞
二、作业
1. 南方小土豆
/*
思路:
相连的一样的农作物可以被认为是一块，
可以采用搜索来访问每个点。每访问到一个字符表示该农作物的块数加 1，通过搜索 4 个方向，
得到这个点连通的所有一样的的农作物，将这些点标记，表示属于同一块。
下次搜索我们搜索的是没有被访问过的点，如果这些点存在，表示属于一个全新一块，
我们继续搜索 4 个方向。对于每一次的搜索，我们要记录 该连通块属于哪一种农作物。
*/
#include<bits/stdc++.h>
using namespace std;
char mp[105][105];
int n, m, bucket[10];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
bool vis[105][105];
void dfs(int x, int y, char ch){
mp[x][y] = '0';
for (int i=0; i<4; i++){
int a = x + dir[i][0], b = y + dir[i][1];
if (a<1 || a>n || b<1 || b>m || mp[a][b]!=ch || mp[a][b] == '0')
continue;
dfs(a, b, mp[a][b]);
}
}
int main(){
cin >>n >>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
cin>>mp[i][j];
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
if (mp[i][j]=='0') continue;
bucket[mp[i][j]-48]++;
dfs(i, j, mp[i][j]);
}
}
for (int i=1; i<=9; i++) cout<<bucket[i]<<' ';
return 0;
}
/*
[南方小土豆]
题目描述
为了迎接南方小土豆，东北文旅局在一片肥沃的黑土地上面，
用一个 N×M(1≤N≤100,1≤M≤100) 的网格图表示，一共种植了9 种农作物，我们用数字 1～9 表示 。
一个网格与其周围的四个网格相连，而一组相连的同一种农作物网格视为同一块。
小码君想弄清楚黑土地上这 9 种农作物各自有多少块。
输入格式
输入第 1 行：两个空格隔开的整数：N 和 M。
第 2 行到第 N+1 行：每行 M 个字符，每个字符是 1～9 其中的一个，它们表示网格图中的一排。
字符之间没有空格。
输出格式
输出一行 9 个数，每个数之间用一个空格隔开。第 i 个数表示第 i 种农作物的块数。
样例组
输入#1
5 4
1315
1119
1223
1221
4111
输出#1
2 1 2 1 1 0 0 0 1
*/
2. 红与黑
/*
@可以看做为起点，我们可以记录起点的坐标，只能向相邻的方向移动到黑色瓷砖，相当于四个方向。
对于移动，我们可以用深度优先搜索来实现。
对于每次移动到的黑色瓷砖，我们可以标记，表示已经走过，则下次就不能再走，能够避免重复，同时要记录数量。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 29;
//1、定义变量n、m、变量sum统计答案、方向数组、二维字符数组、标记数组
int n , m , sum;
char mp[maxn][maxn];
bool vis[maxn][maxn];
int to[4][2] = {-1 , 0 , 0 , 1 , 1 , 0 , 0 , -1};
void dfs(int x , int y){
//5、从(x,y)出发遍历4个方向
for(int i = 0; i < 4; i++){
int tx = x + to[i][0] , ty = y + to[i][1];
//6、判断(tx,ty)是否符合题意
if(tx >= 0 && tx < n && ty >= 0 && ty < m && mp[tx][ty] == 'B' && !vis[tx][ty]){
//7、符合题意，标记，数量增加，递归
vis[tx][ty] = true;
sum++;
dfs(tx , ty);
}
}
}
int main(){
//2、输入地图的大小以及地图
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> mp[i];
//3、定义bx，by，找到起点的坐标
int bx , by;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(mp[i][j] == '@')
{
bx = i;
by = j;
}
}
}
//4、从起点开始进行深度优先搜索
sum = 1;
dfs(bx , by);
//8、输出答案
cout << sum << endl;
return 0;
}
/*
[红与黑]
题目描述
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。
请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
输入格式
第一行为两个整数 n 和 m，表示长方形的行列。n 和 m 都不超过 20。
在接下来的 n 行中，每行包括 m 个字符。每个字符表示一块瓷砖的颜色，
规则如下:
1）‘B’：黑色的瓷砖；
2）‘R’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符仅出现唯一一次。
输出格式
一个整数，表示你从初始位置出发能到达的黑色瓷砖数(记数时包括初始位置的瓷砖)。
样例组
输入#1
9 6
BBBBRB
BBBBBR
BBBBBB
BBBBBB
BBBBBB
BBBBBB
BBBBBB
R@BBBR
BRBBRB
输出#1
45
提示
样例分析：
从@出发，一共能够到达 45 个黑色瓷砖。如下图圈内所示：
*/
这里空空如也
有帮助，赞一个