http://poj.org/problem?id=1027
题意：给一个10*15的地图，里面填充R,G,B三种颜色，每次找到当前地图的同色最大区域M，并将其删除，删除M后，上面的小球自然下落，当有空列时，空列右边的小球同时向左移动一列，
当最后地图上同色最大区域的小球个数是1或0时，循环结束；注意输出格式，最后输出一个空行。
思路：
while(true)
{
找到同色最大区域，包括其面积Maxsize，坐标，颜色（BFS，手写队列）;
if (Maxsize == 1 || Maxsize == 0) break;
删除该最大区域，即将map[i][j] 置为0，（BFS,手写队列）；
重置地图；
输出；
}
#include<stdio.h>
#include<string.h>
char map[][];
bool vis[][];
int MaxR,MaxC;//分别存同色最大区域左下角坐标
int Maxsize;//Maxsize存最大面积
char Maxcolor;//最大同色区域的颜色； int Area(int i,int j)//搜索当前同色区域面积
{
struct node
{
int x,y;
}que[]; int head,tail;
head = tail = ; que[tail].x = i;
que[tail++].y = j;
vis[i][j] = true; char color = map[i][j];
int size = ;
while(head < tail)
{
int x = que[head].x;
int y = que[head++].y;
size++; if((x+)< && !vis[x+][y] && map[x+][y] == color)
{
que[tail].x = x+;
que[tail++].y = y;
vis[x+][y] = true;
}
if((x-)>= && !vis[x-][y] && map[x-][y] == color)
{
que[tail].x = x-;
que[tail++].y = y;
vis[x-][y] = true;
}
if((y-)>= && !vis[x][y-] && map[x][y-] == color)
{
que[tail].x = x;
que[tail++].y = y-;
vis[x][y-] = true;
}
if((y+)< && !vis[x][y+] && map[x][y+] == color)
{
que[tail].x = x;
que[tail++].y = y+;
vis[x][y+] = true;
}
}
return size;
} void SearchArea()//搜索同色最大区域；
{
int i,j;
memset(vis,false,sizeof(vis));
Maxsize = ;
for(j = ; j < ; j++)
{
for(i = ; i < ; i++)
{
int size = -;
if(!vis[i][j] && map[i][j])
{
size = Area(i,j);
if(size > Maxsize)
{
Maxsize = size;
MaxR = i;
MaxC = j;
Maxcolor = map[MaxR][MaxC];
}
}
}
}
} void DelArea()//删除最大区域
{
struct node
{
int x,y;
}que[];
int head,tail;
head = tail = ;
que[tail].x = MaxR;
que[tail++].y = MaxC; Maxcolor = map[MaxR][MaxC];
map[MaxR][MaxC] = ; while(head < tail)
{
int x = que[head].x;
int y = que[head++].y;
map[x][y] = ; if(x+ < && map[x+][y] == Maxcolor)
{
map[x+][y] = ;
que[tail].x = x+;
que[tail++].y = y;
}
if(x- >= && map[x-][y] == Maxcolor)
{
map[x-][y] = ;
que[tail].x = x-;
que[tail++].y = y;
}
if(y- >= && map[x][y-] == Maxcolor)
{
map[x][y-] = ;
que[tail].x = x;
que[tail++].y = y-;
}
if(y+ < && map[x][y+] == Maxcolor)
{
map[x][y+] = ;
que[tail].x = x;
que[tail++].y = y+;
}
}
} void NewMap()//重置
{
bool empty[] = {false};//记录哪一列是空列
int i,j;
for(j = ; j < ; j++)//重置行
{
int ti = -;//表示第ti行是空的，ti = -1 表示现在没有空行；
bool flag = false;
for(i = ; i < ; i++)
{
if(map[i][j])
{
flag = true;
if(ti != -)
{
map[ti][j] = map[i][j];//将第i行移至第ti行
map[i][j] = ;//将第i行置0；
i = ti;//从ti行开始再一次枚举；
ti = -;
}
}
else
{
ti = i;
while(i+ < && !map[i+][j])
i++;
}
}
if(!flag)
empty[j] = true;
}
int tj = -;//表示第tj列是空的，tj = -1说明现在好没有空列
for(j = ; j < ; j++)//重置列
{
if(!empty[j])//如果第j列是不空的
{
if(tj != -)
{
for(i = ; i < ; i++)
{
map[i][tj] = map[i][j];
map[i][j] = ;
}
empty[j] = true;
j = tj;
tj = -;
}
}
else
{
tj = j;
while(j+< && empty[j+])
j++;
}
}
} int main()
{
int test;
scanf("%d",&test);
for(int item = ; item <= test; item++)
{
for(int i = ; i >= ; i--)
scanf("%s",map[i]); printf("Game %d:\n\n",item); int Balls = ;
int step = ;
int sumscore = ;
while(true)
{
Maxsize = -;
SearchArea();//寻找同色最大区域；
if(Maxsize == || Maxsize == )
break; DelArea();//删除当前最大区域
NewMap();//重置 int score = (Maxsize-)*(Maxsize-);
printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",++step,MaxR+,MaxC+,Maxsize,Maxcolor,score);
Balls = Balls - Maxsize;
sumscore += score;
}
if(Balls == )
sumscore += ;
printf("Final score: %d, with %d balls remaining.\n\n",sumscore,Balls);
}
return ;
}