链接：https://ac.nowcoder.com/acm/contest/558/J 来源：牛客网
题目描述
小猫在研究网格图。
小猫在研究联通性。
给定一张N×M的网格图，只含字符0和1，问1形成的联通块有多少个。
两个1是联通的，当且仅当其中一个位于另一个的上、下、左、右四个方向之一。
输入描述:
第一行一个正整数T，表示数据组数。
每组数据的第一行两个正整数N,M，表示矩阵的长和宽。
接下来N行，每行M个字符0或1。
输出描述:
T行，每行一个正整数，表示每组数据的答案。
示例1
输入
复制
2
3 5
10101
01110
10101
3 3
111
010
111
输出
复制
5
1
备注:
1≤T,N,M≤50
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <list>
#include <set>
using namespace std;
const int MAX = 55;
char map[MAX][MAX];
bool vis[MAX][MAX];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int a,b;
int cnt = 0;
void dfs(int x,int y){
vis[x][y] = true;
for(int i=0;i<4;i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx>=0 && xx<a && yy>=0 && yy<b && map[xx][yy] == '1' && !vis[xx][yy]){
dfs(xx,yy);
}
}
}
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=0;i<n;i++){
cnt = 0;
memset(vis,false,sizeof(vis));
cin>>a>>b;
for(int j=0;j<a;j++){
for(int k=0;k<b;k++){
cin>>map[j][k];
}
}
for(int j=0;j<a;j++){
for(int k=0;k<b;k++){
if(!vis[j][k] && map[j][k] == '1'){
cnt++;
dfs(j,k);
}
}
}
cout<<cnt<<endl;
}
return 0;
}
