Description
题目描述
给出一个n×m 的 01 矩阵，求其中最大的一个全为 1 的连通块。
其中连通按四连通计算，即相邻两个格子都是 1 算连通，但斜着的两个格子不算连通。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 T，表示数据的组数。保证T=5。
对于每个部分，第一行包含两个正整数 n 和 m，保证 1≤n,m≤1000。
接下来 n 行，每行为一个长度为 m 的字符串，表示每个格子的情况。为 0 表示格子为白色，为 1 表示格子为黑色。保证至少有一个黑色的格子，保证不会出现其他字符。
输出格式
输出到标准输出。
输出 T 行，每行一个整数，表示最大的全为 1 的连通块。
样例1输入
5
1 20
11111000000011010101
1 20
01011111001000101000
1 20
00000100100000000000
1 20
10000110010000111001
1 20
01110000001000001010
样例1输出
5
5
1
3
3
样例2输入
5
5 5
10011
00110
01010
11110
11010
5 5
00000
00000
00000
00000
00100
5 5
01100
10011
10110
10101
10100
5 5
00101
10111
10001
01011
11011
5 5
01110
01101
11000
00110
10010
样例2输出
13
1
6
10
7
子任务
对于测试点 1，保证 n=1,m=10。
对于测试点 2，保证 n=1,m=1000。
对于测试点 3，保证 n=4,m=4。
对于测试点 4，保证n=5,m=6。
对于测试点 5，保证n=1000,m=1000。
这道题显然是深度优先搜素，跟求能够走多少个格子的题目是一样一样的，所以我们直接深度优先遍历，用标记数组标记就可以了（记得清空）
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,maxn=INT_MIN;
int dr[4][2]={{0,1},{0,-1},{1,0},{-1,0}},used[1100][1100];
char a[1100][1100];
void dfs(int x,int y){
maxn=max(maxn,cnt);
if (x>n||y>m||x<1||y<1)return;
for (int i=0;i<4;i++){
int rx=x+dr[i][0],ry=y+dr[i][1];
if (used[rx][ry]==0&&a[rx][ry]=='1'){
used[rx][ry]=1;
cnt++;
dfs(rx,ry);
}
}
return;
}
int main(){
int T;
cin>>T;
for (int t=0;t<T;t++){
maxn=INT_MIN;
memset(used,0,sizeof(used));
cin>>n>>m;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (a[i][j]=='1'&&used[i][j]==0){
cnt=1;
used[i][j]=1;
dfs(i,j);
// cout<<cnt<<endl;
}
}
}
cout<<maxn<<endl;
}
return 0;
}
