Bubble Shooter

Bubble shooter is a popular game. You can find a lot of versions from the Internet. The goal of this game is to clean the bubbles off the field. Every time you just point the cannon to where you want the next bubble to go, and if three or more of bubbles with the same color came together (including the newly shot bubble), they will detonate. After the first explode, if some bubbles are disconnected from the bubble(s) in the topmost row, they will explode too. In this problem, you will be given an arranged situation of bubbles in the field and the newly shot bubble. Your program should output the total number of bubbles that will explode.

There are multiple test cases. Each test case begins with four integers H (the height of the field, 2 <= H <= 100), W (the width of the field, 2 <= W <= 100, in the picture above, W is 10), h (the vertical position of the newly shot bubble, count from top to bottom, and the topmost is counted as 1) and w (the horizontal position of the newly shot bubble, count from left to right, and the leftmost is counted as 1). Then H lines follow, the odd lines will contain W characters while the even lines will contain W-1 characters (refer to the picture above). Each character will be either a lowercase from 'a' to 'z' indicating the color of the bubble in that position, or a capital letter 'E' indicating an empty position. You may assure the arranged situation is always valid (all the bubbles are directly or indirectly connected with at least one bubble in the topmost row, and the position of newly shot bubble is never empty).

For each test case, output an integer indicating how many bubbles will explode.

2 2 2 1aaa3 3 3 3aaababba3 3 3 1aaababba3 3 3 3aaaEaaab

3830

JIN, Tianpeng

/*题目意思是： 给你一个H*W的矩阵，奇数行w个，偶数行w-1个字符，E代表空，a-z代表的不同的颜色，给你一个起始坐标h,w，作为新射进去的泡泡，如果周围连着有三个（算上自己），则连着的一起爆炸，如果剩下的没连着顶行也会掉下来，问有多少掉下来 网上注解：题意：其实就是泡泡龙的游戏，给你起始的地图，以及刚打出去的泡泡的位置，如果与刚打出的泡泡相连的泡泡数大于等于3，则相连的相同颜色的泡泡会掉下来，之后，没有与顶层泡泡直接或间接相连的泡泡也会掉下来。问掉下来的泡泡总数。 *//*思路：对起始泡泡进行广搜，标记，然后枚举顶层存在的泡泡广搜进行染色，剩下的和刚才爆炸的即为掉下来的 注意：坑死我了！！

奇偶行的连接点并不一样啊 看图！！！和下面的分析！*/#include
    
     #include 
     
      #include 
      
       using namespace std;const int N=100+5;char map[N][N];bool book[N][N];int re;struct Node{	int x,y;}node,tmp;queue
       
         q;//方向错了！这里要看图 排列的时候是交叉的//例如偶数行时/*0 1 10 X 11 1 1//奇数行时1 1 01 X 11 1 0*/int step2[6][2]={
   {-1,0},{-1,1},{0,-1},{0,1},{1,0},{1,1}}; //oddint step1[6][2]={
   {-1,-1},{-1,0},{0,-1},{0,1},{1,-1},{1,0}};int main(){      int n,m,x,y;    while(cin>>n>>m>>x>>y){    	re=0;    	while(!q.empty())  q.pop();    	memset(book,0,sizeof(book));    	for(int i=0;i
        
         >map[i];    		if((i+1)%2==0)    		  map[i][m-1]='E';		}		/*for(int i=0;i
         
          =n||b>=m) continue; if(book[a][b]||map[a][b]=='E') continue; if(map[a][b]!=map[tmp.x][tmp.y]) continue; re++; node.x=a; node.y=b; book[a][b]=1; q.push(node); } } //注意 //注意 //注意 //如果有3个或以上泡泡爆炸，则继续，否则结束 //- _ -!! 这种做法是错误的？ //因为1） num<3 。 //那么要将之前的标记清除， //找出与顶层泡泡直接相连或间接相连的泡泡总数ans， //all-ans就是答案了。这里解决了一个特殊情况， // 本来以为num<3的话，直接输出０就可以了，但其实很有可能， // 即使ｎｕｍ＜３，但起始的地图也会有一些泡泡会掉下来。 if(re<3) { //cout<<0<
          
           =n||a<0||b<0||b>=m) continue; if(book[a][b]||map[a][b]=='E') continue; book[a][b]=1; node.x=a; node.y=b; q.push(node); } } } } //查找剩下的 for(int i=0;i