简单的DFS搜索，求出连通块个数
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 350; 4 char mp[maxn][maxn],flag[maxn][maxn]; 5 int head[4][2]={{0,-1},{1,0},{0,1},{-1,0}}; //四个方向 6 int n, m ,q, ans; 7 8 void dfs(int x,int y) 9 { 10 mp[x][y] = '0'; //标记访问过，不能再访问 11 for(int i = 0; i < 4; i++) 12 { 13 int dx = x + head[i][0]; //x方向 14 int dy = y + head[i][1]; //y方向 15 if(mp[dx][dy]=='1' && dx>=1 && dx<= n&& dy>=1 && dy<=m) //在地图中搜索 16 { 17 mp[dx][dy] = '0'; //标记访问过 18 dfs(dx,dy); //递归搜索 19 } 20 } 21 } 22 int main() 23 { 24 cin>>n>>m; 25 for(int i = 1; i <= n; i++) //输入n行 m 列 的地图 26 for(int j = 1; j <= m; j++) 27 cin>>mp[i][j]; 28 cin>>q; 29 while(q--) 30 { 31 ans = 0; 32 int x1, y1, x2, y2; 33 cin>>x1>>y1>>x2>>y2; 34 for(int i = x1; i <= x2; i++) //x1，y1到 x2,y2 区域的数字变为 1 35 for(int j = y1; j <= y2; j++) 36 mp[i][j] = '1'; 37 38 for(int i = 1; i <= n; i++) 39 for(int j = 1; j <= m; j++) 40 flag[i][j]=mp[i][j]; //保存当前状态 41 42 for(int i = 1; i <= n; i++) //搜索 43 { 44 for(int j = 1; j <= m; j++) 45 { 46 if(mp[i][j] == '1') 47 { 48 ans++; //；连通块个数加1 49 dfs(i,j); 50 } 51 } 52 } 53 54 for(int i = 1; i <= n; i++) 55 for(int j = 1; j <= m; j++) 56 mp[i][j]=flag[i][j]; //搜索后还原搜索前的图 57 printf("%d ",ans); //输出连通块个数 58 } 59 return 0; 60 }