题目大意：
泡泡龙是一款十分受欢迎的游戏。你能在因特网上找到许多版本的泡泡龙。游戏的目标是清除屏幕中泡泡。每次你可以发射一个泡泡到一个区域，如果有三个或者更多的相同颜色的泡泡在一起（包括你刚刚发射上去的），它们就会被引爆。第一次爆炸后，如果一些泡泡与最顶上一行的泡泡断开了，它们同样也会爆炸。
在本题的问题中，是将给你一个随机的泡泡区域和最近发射上去的泡泡坐标。你的程序任务是输出一共有多少个泡泡会爆炸。
输入：
将有许多组测试数据。每组测试将以四个整数开始：H（区域的高度，2 <= H <= 100），W（区域的宽度，2 <= W <= 100，在上面的图片中，W是10），h（最近发射上去的泡泡的竖直位置，计数方式从顶部至底部，最顶部为第1行），w（最近发射上去的泡泡的水平位置，计数方式从左至右，最左边为第1列）。
接下来后面跟着H行，奇数行包含W个字符，偶数行包含W-1个字符（参考上面的图片）。每个字符要么是‘a’到‘z’中的一个小写字母，表明在这个位置上泡泡的颜色，要么是一个字母‘E’，表明一个空位置。你可以认为给出的测试例子符合实际游戏情况，没有bug（所有的泡泡直接或者间接与最顶上的一行的泡泡相连，最近发射上去的泡泡的位置不为空）。
输出：
对于每个测试，输出一个整数，表明有多少泡泡会爆炸。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 const int oddDir[6][2] = { { -1, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 } }; //奇数行泡泡的移动的方向 6 const int evenDir[6][2] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 0, -1 } }; //偶数行泡泡的移动的方向 7 const int N = 110; 8 char board[N][N]; //棋盘 9 bool visit[N][N]; //记录访问泡泡的情况 10 int H, W, h, w; //棋盘高度、棋盘宽度、起始点(h-1, w-1) 11 char bubbleColor; //记录起始的泡泡颜色 12 int bubbles; //记录炸掉的泡泡数量 13 14 /* 初始化函数 */ 15 void init(void) 16 { 17 h -= 1; //题目给出的坐标是从1开始计数，程序中的坐标从0开始，因此处理一下题目给出的坐标 18 w -= 1; 19 bubbles = 0; 20 memset(board, 0, sizeof(board)); 21 memset(visit, 0, sizeof(visit)); 22 } 23 24 /* 第一种dfs搜索，从(h,w)开始出发，记录与(h,w)位置相邻并且颜色相同的泡泡数量(记录到bubbles里头) */ 25 void dfs(int row, int col) 26 { 27 int r, c; 28 for (int i = 0; i < 6; ++i) 29 { 30 if (0 == (row+1) % 2)//偶数行 31 { 32 r = row + evenDir[i][0]; 33 c = col + evenDir[i][1]; 34 } 35 else //奇数行 36 { 37 r = row + oddDir[i][0]; 38 c = col + oddDir[i][1]; 39 } 40 if (0 <= r && r < H && 0 <= c && c < W && false == visit[r][c] && bubbleColor == board[r][c]) 41 { 42 visit[r][c] = true; 43 bubbles++; 44 dfs(r, c); 45 } 46 } 47 } 48 49 /* 第二种dfs搜索，从(row,col)出发，count：记录所有与(row,col)相邻的没有爆炸的泡泡数量; heigth：记录这些泡泡能连接到的最顶层的泡泡行数*/ 50 void dfsPro(int row, int col, int &count, int &height) 51 { 52 int r, c; 53 for (int i = 0; i < 6; ++i) 54 { 55 if (0 == (row + 1) % 2)//偶数行 56 { 57 r = row + evenDir[i][0]; 58 c = col + evenDir[i][1]; 59 } 60 else //奇数行 61 { 62 r = row + oddDir[i][0]; 63 c = col + oddDir[i][1]; 64 } 65 if (0 <= r && r < H && 0 <= c && c < W && false == visit[r][c] && 'a' <= board[r][c] && board[r][c] <= 'z') 66 { 67 visit[r][c] = true; 68 count++; 69 if (height > r) //如果遇到的泡泡行数比之前的行数要小，就更新，表示这一堆相连的泡泡所能连接到的最上面泡泡的行数 70 height = r; 71 dfsPro(r, c, count, height); 72 } 73 } 74 } 75 76 int main(void) 77 { 78 while (scanf("%d %d %d %d", &H, &W, &h, &w) != EOF) 79 { 80 init(); 81 for (int i = 0; i < H; ++i) 82 { 83 scanf("%s", board[i]); 84 for (int j = 0; j < W; ++j) 85 if ('E' == board[i][j]) //处理'E'方便后面对空位置操作统一 86 board[i][j] = ' '; 87 } 88 89 //搜索之前，先初始化bubbles，bubbleColor，visit[h][w] 90 bubbles++; 91 bubbleColor = board[h][w]; 92 visit[h][w] = true; 93 94 //第一种dfs 95 dfs(h, w); 96 97 //泡泡数至少大于等于3，泡泡才会爆炸 98 if (bubbles <= 2) 99 { 100 printf("0 "); 101 continue; 102 } 103 104 for (int i = 0; i < H; ++i) 105 for (int j = 0; j < W; ++j) 106 if (false == visit[i][j] && 'a' <= board[i][j] && board[i][j] <= 'z') 107 { 108 //搜索之前，先初始化count，row，visit[i][j] 109 int count = 1; 110 int row = i; 111 visit[i][j] = true; 112 113 //第二种dfs搜索 114 dfsPro(i, j, count, row); 115 116 //当row不为0的时候，表示这堆泡泡没有与最顶层的泡泡相连，全部会爆炸 117 if (row > 0) 118 bubbles += count; 119 } 120 121 printf("%d ", bubbles); 122 } 123 return 0; 124 }