2021寒假刷题 || 洛谷P1451 / DFS初学
文章目录

大致思路:
DFS介绍:
- 深度优先搜索(depth-first searching,dfs)
- 优先向深处搜索,直到无法找到新的分支时再回溯。
- 由于需要反复地前进、回溯,适合使用递归来实现。
- 具体地,可以在函数中枚举所有的分支,然后依次进行递归调用。
#include<bits/stdc++.h>
using namespace std;
char cell[105][105];
int n,m;
void dfs(int i,int j){
cell[i][j]='0';
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
for(int k = 0;k < 4;k++){
int xx = i + dx[k],yy = j + dy[k];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&cell[xx][yy]!='0'){
dfs(xx,yy);
}
}
}
int main(){
cin>>n>>m;
/* for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
cin>>cell[i][j];
开始写的时候没有看输入格式,它是一串一串的,所以不能一个个输入,并且该用char数组而不是int
*/
for(int i = 0;i < n;i++)
cin>>cell[i];
int ans = 0;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++){
if(cell[i][j] != '0'){
ans++;
dfs(i,j);
}
}
cout<<ans<<endl;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论