2018.8.16 2018暑假集训之球迷
球迷
【问题描述】
一个球场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×103。
突然想抱怨两句
本题为今日头条笔试题 原来的数据范围是100*100 然鹅老师为了尊重我们的智商放到了3000*3000加上字符串
由于有一个可恶的TLE 所以本题明显不能用裸的bfs（queue实在太慢了）
本人水平有限不会优化bfs 所以在这里采用dfs
于是本题便转化成了一个不用回溯的dfs问题
那么问题来了：咋dfs？为什么不需要回溯？？？（来自已经快忘了dfs的蒟蒻）
我们首先复习一下啥是dfs
其实就是从一个方向搜完一整条路线再搜下一条路线
对于一般的dfs（可以参照全排列等经典例题）由于每一种情况都要考虑到所以需要回溯
但是对于本题来讲并不存在“走和不走”的逻辑矛盾所以并不需要回溯
咋搜看代码吧
#include<iostream> using namespace std; int m,n,cnt,tmp,maxn;//cnt存储有几组 tmp存储每组几个 maxn存储最多人数 char ch,map[3050][3050];//为了防止MLE以及TLE把地图存成字符 ch用来读',' static const int dx[8]={-1,1,0,0,-1,-1,1,1},dy[8]={0,0,-1,1,-1,1,1,-1};//方向数组 inline int read() { int x,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0'); return x*f; }//读入优化 本质上还是getchar() 注意cin会TLE void dfs(int x,int y)//dfs x、y是横纵坐标 { for(int i=0;i<8;i++)//八个方向 { int tx=x+dx[i],ty=y+dy[i];//目标点 if(map[tx][ty]=='1'&&tx>0&&tx<=m&&ty>0&&ty<=n)//可以到达而且不会越界 { tmp++;//本组人数加一 map[tx][ty]='0';//避免重复经过（很重要的剪枝） dfs(tx,ty);//递归搜索下一个目标点 } } return;//八个方向都搜不到就返回下一条路 } int main() { m=read(),ch=getchar(),n=read();//ch处理逗号 for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { ch=getchar(); map[i][j]=getchar(); } }//划重点！！！ //前面我们已经提到过了m，n后面会有一个回车 //而getchar是会读回车的 //所以对于每一个点我们在读入时可以划分成两个部分：一个字符（回车或逗号）+键值 for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(map[i][j]=='1')//找到一个可以开始搜索的点 { cnt++;//增加一组 dfs(i,j);//从当前位置搜索 if(tmp>maxn)maxn=tmp;//更新人数最大值 tmp=0; //注意归零 } } } printf("%d,%d",cnt,maxn); return 0; }
本题是一道经典的dfs例题 可供大家参考学习