题意:给你一副图n行m列，其中’W’代表池塘，’.'代表土地，问现在这幅图中有多少个池塘，如果一个池塘的八个方向上如果有池塘，则只算一个,类似于连通块,求有多少个连通块。
思路:bfs和dfs
BFS
用队列实现，需要用到pair或者结构体存储下标，通过找到一个w然后用队列实现连通功能的块。
#include<iostream> #include<queue> #include<map> using namespace std; const int maxn = 105; char a [maxn][maxn]; pair<int ,int >m1; typedef pair<int ,int >P; queue<pair<int ,int > >mo; void bfs(int x,int y ,int n ,int m){ int i,j; while(!mo.empty()){ P d = mo.front(); mo.pop(); for(i=-1;i<=1;i++){ for(j=-1;j<=1;j++){ int x1,y1; x1=d.first+i,y1=d.second+j; if(x1>=0&&x1<n&&y1>=0&&y1<m&&a[x1][y1]=='W'){ a[x1][y1]='.'; mo.push(P(x1,y1)); } } } } } int solve(int n, int m ){ int ans = 0,i,j; for(i = 0 ;i < n ; i++){ for( j = 0 ;j < m ;j++){ if(a[i][j]=='W'){ ans++; mo.push(P(i,j)); bfs(i,j,n,m); } } } return ans; } int main() { int n , i , j , m ; cin >> n >> m; for(i = 0; i < n; i ++){ for(j = 0; j < m ;j++) cin >> a[i][j]; } int ans=0; ans=solve(n,m); cout << ans <<endl; }
DFS
查找到了为水坑的低点之后就继续搜索不断查找=。=
#include<iostream> using namespace std; const int maxn = 105; char a [maxn][maxn]; void dfs(int x, int y,int n,int m ){ int i,j,b,c; for(i = -1;i <= 1;i++){ for(j = -1 ;j <=1 ;j++){ b=i+x; c=y+j; if(b>=0&&b<n&&c>=0&&c<m&&a[b][c]=='W'){ a[b][c]='.'; dfs(b,c,n,m); } } } } int solve (int n,int m ){ int ans = 0,i,j; for(i = 0; i < n ;i ++){ for( j = 0 ; j < m ;j ++){ if(a[i][j]=='W'){ dfs(i,j,n,m); ans++; } } } return ans; } int main() { int n , i , j , m ; cin >> n >> m; for(i = 0; i < n; i ++){ for(j = 0; j < m ;j++) cin >> a[i][j]; } int ans=0; ans=solve(n,m); cout << ans <<endl; }
