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 ;
}
05-11 17:28