学习目标
本节课主要学习一种类型的深度优先搜索-连通块
[数水坑]
【思路分析】
相连的水坑可以被认为是一个水坑，求水坑的个数，就是求连通块的个数。
可以采用搜索来访问每个点。每访问到一个 W 表示至少有一个水坑，通过搜索 8 个方向，得到这个点连通的所有的 W，将这些点标记，表示属于一个水坑。下次搜索我们搜索的是没有被访问过的 W，如果这些点存在，表示属于一个全新的水坑，我们继续搜索 8 个方向，标记和这个点连通的 W。对于搜索，采用深度优先和广度优先都是能够解决的，给出深度优先的详细思路和代码以及广度优先的代码。
1、定义变量n,m,字符数组存地图，变量sum统计个数，二维vis数组标记每个点是否访问 定义方向数组
2、输入n，m，以及地图
3、遍历地图的每个点
4、搜索未被访问且是水坑的点
5、标记当前点，遍历8个方向,看每个点是否符合题意
6、输出答案
【参考代码1】
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 9;
//1、定义变量n,m,字符数组存地图，变量sum统计个数，二维vis数组标记每个点是否访问 定义方向数组
int n , m;
char mp[maxn][maxn];
int sum;
bool vis[maxn][maxn];
int to[8][2] = {-1 , 0 , -1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1, -1 , 0 , -1 , -1 , -1};
void dfs(int x , int y){
//5、标记当前点，遍历8个方向,看每个点是否符合题意
vis[x][y] = true;
for(int i = 0; i < 8; 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] == 'W')
dfs(tx , ty);
}
}
int main(){
//2、输入n，m，以及地图
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> mp[i];
//3、遍历地图的每个点
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
//4、搜索未被访问且是水坑的点
if(!vis[i][j] && mp[i][j] == 'W'){
dfs(i , j);
sum++;
}
}
}
//6、输出答案
cout << sum;
return 0;
}
参考代码1
【参考代码2】
#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;
return 0;
}
参考代码2
[填涂颜色]
【思路分析】
这道题的关键就是如何把闭合圈外围的 0 和闭合圈内部的 0区别开。
对于外围的 0，我们可以使用搜索，把能够搜索到的 0打一个标记，最终通过这个标记来输出。
但是随之而来的问题是我们用一次搜索无法将外围的 0全部搜到。就像样例，左上角的 0和 右下角的 0属于两部分，这两部分无法产生联系。
我们可以在地图的外围补一圈 0,让闭合圈外围的 0能够连贯，这样在搜索的时候就能搜索到外围全部的 0。其实把数组开在全局，就默认的补一圈 0。
本来的地图范围为 1~n、1~n，补一圈 0之后，地图的范围为 0~n+1、0~n+1。
我们从外围任意一个 0的位置开始搜索，把能搜索到的 0标记。最后输出的时候，对于 1原样输出；对于 0，有标记的原样输出，没有标记的变为 2输出。
1、定义变量n，二维数组mp存地图，二维标记数组vis，方向数组
2、输入方阵的大小和方阵
3、从任意一个外围0开始搜索，比如(0,0)
4、标记，遍历4个方向
5、输出，对于1原样输出，对于0判断标记输出
【参考代码1】
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 39;
//1、定义变量n，二维数组mp存地图，二维标记数组vis，方向数组
int n , 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){
//4、标记，遍历4个方向
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 + 1 && ty >= 0 && ty <= n + 1 && !vis[tx][ty] && mp[tx][ty] == 0)
dfs(tx , ty);
}
}
int main(){
//2、输入方阵的大小和方阵
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
cin >> mp[i][j];
}
//3、从任意一个外围0开始搜索，比如(0,0)
dfs(0 , 0);
//5、输出，对于1原样输出，对于0判断标记输出
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(mp[i][j] == 0){
if(vis[i][j])
cout << 0 << " ";
else
cout << 2 << " ";
}
else
cout << 1 << " ";
}
cout << endl;
}
return 0;
}
参考代码1
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50;
int n, g[maxn][maxn];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
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]; // 确保在范围内
if (nx >= 0 && ny >= 0 && nx <= n + 1 && ny <= n + 1 && g[nx][ny] == 0)
dfs(nx, ny);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> g[i][j];
// 从左上角开始找连通块
dfs(0, 0);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (g[i][j] == -1) cout << "0 ";
else if (g[i][j] == 0) cout << "2 ";
else cout << "1 ";
}
cout << endl;
}
return 0;
}
参考代码2
[细胞]
【思路分析】
相连的细胞可以被认为是一个细胞，求细胞的个数，就是求连通块的个数。
可以采用搜索来访问每个点。每访问到一个细胞(1~9)表示至少有一个细胞，通过搜索 4 个方向，得到这个点连通的所有的细胞，将这些点标记，表示属于一个细胞。下次搜索我们搜索的是没有被访问过的细胞，如果这些点存在，表示属于一个全新的细胞，我们继续搜索 4 个方向，标记和这个点连通的细胞。对于搜索，采用深度优先和广度优先都是能够解决的，给出深度优先的详细思路和代码。
1、定义变量n,m,字符数组存地图，变量sum统计个数，二维vis数组标记每个点是否访问 定义方向数组
2、输入n，m，以及地图
3、遍历地图的每个点
4、搜索未被访问且是水坑的点
5、标记当前点，遍历4个方向，找到所有的细胞
6、输出答案
【参考代码1】
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 9;
//1、定义变量n,m,字符数组存地图，变量sum统计个数，二维vis数组标记每个点是否访问 定义方向数组
int n , m;
char mp[maxn][maxn];
int sum;
bool vis[maxn][maxn];
int to[4][2] = {-1 , 0 , 0 , 1 , 1, 0 , 0 , -1};
void dfs(int x , int y){
//5、标记当前点，遍历4个方向,找到所有的细胞
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] >= '1' && mp[tx][ty] <= '9')
dfs(tx , ty);
}
}
int main(){
//2、输入n，m，以及地图
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> mp[i];
//3、遍历地图的每个点
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
//4、搜索未被访问且是细胞的点
if(mp[i][j] >= '1' && mp[i][j] <= '9' && !vis[i][j]){
dfs(i , j);
sum++;
}
}
}
//6、输出答案
cout << sum;
return 0;
}
View Code
计算机知识：
编程语言处在不断的发展和变化中，从最初的机器语言发展到如今的2500种以上的高级语言，每种语言都有其特定的用途和不同的发展轨迹。编程语言并不像人类自然语言发展变化一样的缓慢而又持久，其发展是相当快速的，这主要是计算机硬件、互联网和IT业的发展促进了编程语言的发展。
本节课作业讲解：
稍等，正在整理··· 不过课上已讲解过了
标签：03,tx,标记,U5,C++,int,maxn,&&,搜索 From： https://www.cnblogs.com/jayxuan/p/17982674