其实本题是加强版，原数据是100*100的，老师为了尊重我们的智商加成了3000*3000并进行了字符串处理……
上原题~
球迷
【问题描述】
一个球场C的球迷看台可容纳M*N个球迷。官方想统计一共有多少球迷群体，最大的球迷群体有多少人。
球迷选座特性：同球迷群体会选择相邻座位，不同球迷群体选择不相邻的座位。（相邻包括前后相邻、左右相邻、斜对角相邻）；
给定一个M*N的二位球场，0代表该位置没人，1代表该位置有人，希望输出球队群体个数P,最大的球队群体人数Q。
【输入】
第一行，2个数字，M、N，使用英文逗号隔开。
接下来M行，每行N个数字，使用英文逗号隔开。
【输出】
一行，2数字，P和Q。
【输入输出样例】
fans.in | fans.out |
10,10 0,0,0,0,0,0,0,0,0,0 0,0,0,1,1,0,1,0,0,0 0,1,0,0,0,0,0,1,0,1 1,0,0,0,0,0,0,0,1,1 0,0,0,1,1,1,0,0,0,1 0,0,0,0,0,0,1,0,1,1 0,1,1,0,0,0,0,0,0,0 0,0,0,1,0,1,0,0,0,0 0,0,1,0,0,1,0,0,0,0 0,1,0,0,0,0,0,0,0,0 | 6,8 |
【数据范围】
对于100%的数据，1<=M,N<=3×10。
思路：特殊特判读入，找到有人就进行八连块搜索。
上代码~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int m=,n=,t=,num,maxnum=;
bool fans[][];
char x[];
void reads()//字符串特判读入
{
scanf("%s",&x);
int l=strlen(x);
int i=;
while(x[i]!=',')
{m=m*+x[i]-;i++;}//字符转数字
i++;
while(i<l)
{n=n*+x[i]-;i++;}
return;
}
void readings()
{
int l=n*-;//加上逗号的长度
for(int i=;i<=m;i++)
{
scanf("%s",x);
for(int j=;j<l;j=j+)
fans[i][j/+]=x[j]-;//由于是单个字符就不用累加了
}
return;
}
void dfs(int a,int b)//搜索
{
if(a<||a>m||b<||b>n) return;//越界判断
if(!fans[a][b]) return;//是否坐了人
fans[a][b]=;//该人已经计数并撤去标记以免重复标记
num++;
dfs(a-,b-);//向八连块方向搜索坐在一起的球迷
dfs(a-,b);
dfs(a-,b+);
dfs(a,b-);
dfs(a,b);
dfs(a,b+);
dfs(a+,b-);
dfs(a+,b);
dfs(a+,b+);
return;//记得搜索完后退出去
}
int main()
{
reads();//特殊读入m和n
readings();//读入球迷就座情况
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
if(fans[i][j])
{
t++;//发现一个单独的团体组织
num=;//单个团体计数
dfs(i,j);
if(num>maxnum) maxnum=num;//更新最大值
}
}
}
printf("%d,%d",t,maxnum);//按要求输出
return ;
}