题目大意：
在一个10x15的方阵里填满了RGB三种小球，要求：
1、找到最大的一片相同颜色区域，并删掉，（这片区域相同颜色球必须相邻，且相邻数大于1）。
2、删除完成后，其他小球自然下落填充。先每列向下填充，空的列由右边一列平移补全。
3、当区域内没有球或最大相邻区域的个数为一，游戏结束。
题解：
主函数如下
while (true){
int num = getAllMarked();
if (num <= 1)break;
getMaxMark(num, ++step);
format();
}
其中，getAllMarked从左下角向右上进行深度优先遍历，刷新num值（相同颜色区域大小）
getMaxMark从左下向右上找到连通数为num的点集，并将其标记为‘X’。
注意点：
1. 进行遍历所使用的vis数组
vis[i][j] = mark(i, j, data[i][j]);
该数组当且仅当getAllMarked函数进入时进行初始化，作为地图使用
2. format函数类似于STL库中的unique函数，从左(col = 0)下(row=MAXR - 1)开始，遍历
data[row][col] = data[row - offset][col + blank];
format函数实现如下
void format(){
int col, row, blank = 0, offset;
for (col = 0; col + blank < MAXC; ){ //用blank记录空行的个数
offset = 0; //每列维护一个offset偏移量
for (row = MAXR - 1; row - offset >= 0; ){ //循环结束row或offset变化
if (data[row - offset][col + blank] == 'X')++offset; //跳过
else{
data[row][col] = data[row - offset][col + blank];
--row;
}
}
if (offset == MAXR)++blank; //没有执行赋值操作，该列为空列
else{
for (int i = row; i >= 0; --i)data[i][col] = 'X';
++col; //将要被删除的点赋值，为下次查找排除干扰
}
}
for (int j = col; j < MAXC; ++j)
for (int i = 0; i < MAXR; ++i)
data[i][j] = 'X'; //将空行赋值
}
本题目的完整代码如下，仅供初学者参考
/* POJ 1027 - Same Game
题目大意：
在一个10x15的方阵里填满了RGB三种小球，要求：
1、找到最大的一片相同颜色区域，并删掉，（这片区域相同颜色球必须相邻，且相邻数大于1）。
2、删除完成后，其他小球自然下落填充。先每列向下填充，空的列由右边一列平移补全。
3、当区域内没有球或最大相邻区域的个数为一，游戏结束。
*/
#include <stdio.h>
#define MAXC 15
#define MAXR 10
#define ONLINE_JUDGE
int T, N, M, ans, res, next;
char data[MAXR][MAXC];
int vis[MAXR][MAXC];
int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };
int mark(int y, int x, char color){
int num = 1;
for (int i = 0; i < 4; ++i){
int ny = y + dy[i], nx = x + dx[i];
if (ny >= 0 && ny < MAXR && nx >= 0 && nx < MAXC && (data[ny][nx] == color) && vis[ny][nx] < 0){
vis[ny][nx] = 0;
num += mark(ny, nx, color);
}
}
return num;
}
int getAllMarked(){
for (int i = 0; i < MAXR; ++i)
for (int j = 0; j < MAXC; ++j)
vis[i][j] = -1;
int num = 0;
for (int j = 0; j < MAXC; ++j)
for (int i = MAXR - 1; i >= 0; --i){
if (vis[i][j] < 0 && data[i][j] != 'X'){
vis[i][j] = 0;
vis[i][j] = mark(i, j, data[i][j]);
if (vis[i][j] > num)num = vis[i][j];
}
}
return num;
}
void markX(int y, int x, char color){
data[y][x] = 'X';
for (int i = 0; i < 4; ++i){
int ny = y + dy[i], nx = x + dx[i];
if (ny >= 0 && ny < MAXR && nx >= 0 && nx < MAXC && (data[ny][nx] == color)){
markX(ny, nx, color);
}
}
}
void getMaxMark(int num, int step){
for (int j = 0; j < MAXC; ++j)
for (int i = MAXR - 1; i >= 0; --i){
if (vis[i][j] == num){
int offset = (num - 2)*(num - 2);
printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n", step, MAXR - i, j + 1, num, data[i][j], offset);
res -= num;
ans += offset;
markX(i, j, data[i][j]);
return;
}
}
}
void format(){
int col, row, blank = 0, offset;
for (col = 0; col + blank < MAXC; ){
offset = 0;
for (row = MAXR - 1; row - offset >= 0; ){
if (data[row - offset][col + blank] == 'X')++offset;
else{
data[row][col] = data[row - offset][col + blank];
--row;
}
}
if (offset == MAXR)
++blank;
else{
for (int i = row; i >= 0; --i){
data[i][col] = 'X';
}
++col;
}
}
for (int j = col; j < MAXC; ++j)
for (int i = 0; i < MAXR; ++i)
data[i][j] = 'X';
}
int main(){
#ifndef ONLINE_JUDGE
freopen("sample_input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d", &T);
for (int tc = 1; tc <= T; ++tc){
printf("Game %d:\n\n", tc);
for (int i = 0; i < MAXR; ++i)
scanf("%s", &data[i]);
res = 150;
ans = 0;
int step = 0;
while (true){
int num = getAllMarked();
if (num <= 1)break;
getMaxMark(num, ++step);
format();
}
if (res == 0)ans += 1000;
printf("Final score: %d, with %d balls remaining. \n\n", ans, res);
}
}