HDU - 1547 Bubble Shooter(dfs+连通块+模拟)

题目链接：点击查看

题目大意：模拟泡泡枪游戏，问当击破指定位置的泡泡时，能有多少个泡泡同时爆炸？

题目分析：一个中规中矩的连通块问题，只不过在向四周扩散的时候需要注意的是，奇数行和偶数行的方向有点不一样，并且方向由四个变成了六个，这个在纸上画一下就能很清晰了，和之前做过一个蜂巢的题目很像，也是求连通块的一个题目，求连通块的话我个人比较喜欢用dfs求，因为可以边更新边搜索，时间复杂度最坏是n*m，所以并不会超时或爆栈，回到这个题目上，我们可以分为几个步骤来慢慢处理：

1. 先求出一共有多少个泡泡(sum)，后面会用到
2. 再求出包括指定位置在内有多少同色泡泡(cnt)（在dfs时候我将同色的方块都赋值为‘E’，一个是代替vis，一个是下面计数用）
   1. 若同色泡泡小于三个，则直接输出0，因为根据泡泡枪的规则是无法击破的
   2. 若同色泡泡大于等于三个，进入下一步
3. 遍历一遍第一行
   1. 若都为‘E’，说明剩下所有的球要么都已经爆炸，要么都已经与天花板脱离，直接输出第一步求出的sum即可
   2. 若至少有一个点不为'E'，从这个点开始dfs求连通块的最大面积(ans)
4. 到了这一步说明有部分泡泡还未爆炸，有一部分泡泡被射击爆炸，还有一部分泡泡因为与天花板脱离爆炸，那么最终答案就是sum-ans了

直接模拟上述步骤即可，也算是一大半个模拟题了，dfs求连通块感觉更像是一个辅助的工具了。。

上代码：

#include<iostream>
#include<cstdio> 
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const int N=110;

const int b[2][6][2]={{0,1,0,-1,1,0,-1,0,-1,-1,1,-1},{0,1,0,-1,1,0,-1,0,1,1,-1,1}};

char maze[N][N];

int n,m,x,y;

int cnt,ans,sum;

bool check(int x,int y)//检查边界
{
	if(x<0||x>=n)
		return false;
	if(y<0)
		return false;
	if((x&1)&&y>=m-1)
		return false;
	if(!(x&1)&&y>=m)
		return false;
	return true;
}

void dfs1(int x,int y,char ch)//求有多少个相邻并同色的球
{
	maze[x][y]='E';
	cnt++;
	for(int i=0;i<6;i++)
	{
		int xx=x+b[x&1][i][0];
		int yy=y+b[x&1][i][1];
		if(!check(xx,yy))
			continue;
		if(maze[xx][yy]!=ch)
			continue;
		dfs1(xx,yy,ch);
	}
}

void dfs2(int x,int y)//求有多少个与天花板相连接的球
{
	maze[x][y]='E';
	ans++;
	for(int i=0;i<6;i++)
	{
		int xx=x+b[x&1][i][0];
		int yy=y+b[x&1][i][1];
		if(!check(xx,yy))
			continue;
		if(maze[xx][yy]=='E')
			continue;
		dfs2(xx,yy);
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF)
	{
		for(int i=0;i<n;i++)
			scanf("%s",maze[i]);
		sum=0;//球的总数 
		for(int i=0;i<n;i++)
			for(int j=0;maze[i][j];j++)
			{
				if(maze[i][j]!='E')
					sum++;
			}
		cnt=0;//与射击点相连的同色球个数 
		dfs1(x-1,y-1,maze[x-1][y-1]);
		if(cnt<3)
		{
			printf("0\n");
			continue;
		}
		ans=0;//与天花板相连的球
		for(int i=0;i<m;i++)
			if(maze[0][i]!='E')
				dfs2(0,i);
		printf("%d\n",sum-ans);
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}