poj 1027 The Same Game
共 7755字，需浏览 16分钟
· 2022-06-12
The Same Game
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 7599 | Accepted: 2697 |
Description
The game named "Same" is a single person game played on a 10 \Theta 15 board. Each square contains a ball colored red (R), green (G), or blue (B). Two balls belong to the same cluster if they have the same color, and one can be reached from another by following balls of the same color in the four directions up, down, left, and right. At each step of the game, the player chooses a ball whose cluster has at least two balls and removes all balls in the cluster from the board. Then, the board is "compressed" in two steps:
1. Shift the remaining balls in each column down to fill the empty spaces. The order of the balls in each column is preserved.
2. If a column becomes empty, shift the remaining columns to the left as far as possible. The order of the columns is preserved.
For example, choosing the ball at the bottom left corner in the sub-board below causes:
The objective of the game is to remove every ball from the board, and the game is over when every ball is removed or when every cluster has only one ball. The scoring of each game is as follows. The player starts with a score of 0. When a cluster of m balls is removed, the player's score increases by (m-2)^2 . A bonus of 1000 is given if every ball is removed at the end of the game.
You suspect that a good strategy might be to choose the ball that gives the largest possible cluster at each step, and you want to test this strategy by writing a program to simulate games played using this strategy. If there are two or more balls to choose from, the program should choose the leftmost ball giving the largest cluster. If there is still a tie, it should choose the bottommost ball of these leftmost balls.
Input
You will be given a number of games in the input. The first line of input contains a positive integer giving the number of games to follow. The initial arrangement of the balls of each game is given one row at a time, from top to bottom. Each row contains 15 characters, each of which is one of "R", "G", or "B", specifying the colors of the balls in the row from left to right. A blank line precedes each game.
Output
For each game, print the game number, followed by a new line, followed by information about each move, followed by the final score. Each move should be printed in the format:
Move x at (r,c): removed b balls of color C, got s points.
where x is the move number, r and c are the row number and column number of the chosen ball, respectively. The rows are numbered from 1 to 10 from the bottom, and columns are numbered from 1 to 15 from the left. b is the number of balls in the cluster removed. C is one of "R", "G", or "B", indicating the color of the balls removed. s is the score for this move. The score does not include the 1000 point bonus if all the balls are removed after the move.
The final score should be reported as follows:
Final score: s, with b balls remaining.
Insert a blank line between the output of each game. Use the plural forms "balls" and "points" even if the corresponding value is 1.
Sample Input
3
RGGBBGGRBRRGGBG
RBGRBGRBGRBGRBG
RRRRGBBBRGGRBBB
GGRGBGGBRRGGGBG
GBGGRRRRRBGGRRR
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
RRRRRRRRRRRRRRR
RRRRRRGGGGRRRRR
GGGGGGGGGGGGGGG
RRRRRRRRRRRRRRR
RRRRRRRRRRRRRRR
GGGGGGGGGGGGGGG
GGGGGGGGGGGGGGG
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
RRRRRRRRRRRRRRR
RRRRRRRRRRRRRRR
GGGGGGGGGGGGGGG
GGGGGGGGGGGGGGG
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
Sample Output
Game 1:
Move 1 at (4,1): removed 32 balls of color B, got 900 points.
Move 2 at (2,1): removed 39 balls of color R, got 1369 points.
Move 3 at (1,1): removed 37 balls of color G, got 1225 points.
Move 4 at (3,4): removed 11 balls of color B, got 81 points.
Move 5 at (1,1): removed 8 balls of color R, got 36 points.
Move 6 at (2,1): removed 6 balls of color G, got 16 points.
Move 7 at (1,6): removed 6 balls of color B, got 16 points.
Move 8 at (1,2): removed 5 balls of color R, got 9 points.
Move 9 at (1,2): removed 5 balls of color G, got 9 points.
Final score: 3661, with 1 balls remaining.
Game 2:
Move 1 at (1,1): removed 30 balls of color G, got 784 points.
Move 2 at (1,1): removed 30 balls of color R, got 784 points.
Move 3 at (1,1): removed 30 balls of color B, got 784 points.
Move 4 at (1,1): removed 30 balls of color G, got 784 points.
Move 5 at (1,1): removed 30 balls of color R, got 784 points.
Final score: 4920, with 0 balls remaining.
Game 3:
Final score: 0, with 150 balls remaining.
同样的游戏
描述
这款名为“Same”的游戏是一个在10 \Theta 15板上玩的单人游戏。每个方块中分别有红(R)、绿(G)、蓝(B)三种颜色的球。如果两个球的颜色相同，那么它们就属于同一团球，沿着相同颜色的球从上、下、左、右四个方向移动，就可以到达另一个球。在游戏的每一步中，玩家选择一个集群中至少有两个球的球，并将集群中的所有球从棋盘上移除。然后，板被“压缩”在两个步骤:
1. 将每一列中剩余的球向下移动以填充空白。保留了每一列中球的顺序。
2. 如果某一列变为空，则将其余的列尽量向左移动。列的顺序保留了下来。
例如，在下面的子板中选择左下角的球，原因如下:
游戏的目标是移除棋盘上的每个球，当每个球被移除或每个集群只有一个球时，游戏就结束了。每场比赛的得分如下。玩家以0分开始。当移除一组m个球时，玩家的分数增加(m-2)^2。如果在游戏结束时每个球都被移除，将获得1000的奖励。
您怀疑一个好的策略可能是选择在每一步提供最大可能集群的球，并且您希望通过编写一个程序来模拟使用该策略进行的游戏来测试这个策略。如果有两个或更多的球可供选择，程序应该选择最左边的球，以提供最大的集群。如果仍然有平局，它应该选择这些最左边的球中最下面的球。
输入
你会在输入栏中看到一些游戏。输入的第一行包含一个正整数，表示接下来的游戏数。每个游戏的球的最初安排是一次从上到下的一排。每一行包含15个字符，每个字符都是“R”、“G”或“B”中的一个，从左到右指定了一行中球的颜色。每个游戏前都有一个空行。
输出
对于每一个游戏，打印游戏编号，后面是新的一行，后面是关于每一步的信息，后面是最后的分数。每个动作都应按以下格式打印:
将x移动到(r,c):移除b个颜色为c的球，得到s点。
其中x为移动数，r和c分别为所选球的行号和列号。行从下面编号为1到10，列从左边编号为1到15。B是集群中移除的球的数量。C是“R”、“G”或“B”中的一个，表示被移除的球的颜色。S是这一步的得分。该分数不包括1000点奖金，如果所有的球在移动后被移走。
最终成绩应按以下方式上报:
最后得分:s，剩下b球。
在每个游戏的输出之间插入空行。使用复数形式“balls”和“points”，即使对应的值是1。
Sample Input
3
RGGBBGGRBRRGGBG
RBGRBGRBGRBGRBG
RRRRGBBBRGGRBBB
GGRGBGGBRRGGGBG
GBGGRRRRRBGGRRR
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
RRRRRRRRRRRRRRR
RRRRRRGGGGRRRRR
GGGGGGGGGGGGGGG
RRRRRRRRRRRRRRR
RRRRRRRRRRRRRRR
GGGGGGGGGGGGGGG
GGGGGGGGGGGGGGG
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
RRRRRRRRRRRRRRR
RRRRRRRRRRRRRRR
GGGGGGGGGGGGGGG
GGGGGGGGGGGGGGG
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
Sample Output
Game 1:
Move 1 at (4,1): removed 32 balls of color B, got 900 points.
Move 2 at (2,1): removed 39 balls of color R, got 1369 points.
Move 3 at (1,1): removed 37 balls of color G, got 1225 points.
Move 4 at (3,4): removed 11 balls of color B, got 81 points.
Move 5 at (1,1): removed 8 balls of color R, got 36 points.
Move 6 at (2,1): removed 6 balls of color G, got 16 points.
Move 7 at (1,6): removed 6 balls of color B, got 16 points.
Move 8 at (1,2): removed 5 balls of color R, got 9 points.
Move 9 at (1,2): removed 5 balls of color G, got 9 points.
Final score: 3661, with 1 balls remaining.
Game 2:
Move 1 at (1,1): removed 30 balls of color G, got 784 points.
Move 2 at (1,1): removed 30 balls of color R, got 784 points.
Move 3 at (1,1): removed 30 balls of color B, got 784 points.
Move 4 at (1,1): removed 30 balls of color G, got 784 points.
Move 5 at (1,1): removed 30 balls of color R, got 784 points.
Final score: 4920, with 0 balls remaining.
Game 3:
Final score: 0, with 150 balls remaining.
大致题意：
在一个固定大小为10x15的矩形区域A内被RGB三种颜色的小球填满
现在按如下步骤操作：
1、 删除区域A内最大的一片区域M（任意颜色都可以，只要其占有区域最大）
2、 删除M后，自然会出现空的位置，在M区域上方的小球自然下落；
当删除M后出现空列时，右边的列往左填充。
注意是以“列”为单位填充，非空列只能整列往空列移动。
移动后，各个小球之间的相对顺序 与 移动前一样。
3、 当区域A剩余小球数为0，或A内的最大区域为1时，游戏结束。否则返回1。
输出每一步的得分，最后输出总得分。
解题思路：
没难度的模拟题，直接模拟就可以了，1次AC。
关键在于删除矩形区域M后的刷新地图操作。
寻找最大区域M，和删除M区域都是用BFS执行。
题目要求：区域Z的坐标 = 在区域Z左下角的小球的坐标
因此为了对应坐标，
输入map时，行从9~0输入，列从0~14输入
搜索最大区域时，列从0~14优先搜索，行再从0~9搜索
输出坐标时记得行列+1
代码：
#include
using namespace std;
char map[10][16];
bool vist[10][15];
int MaxSize=-1;
char MaxColor;
int MaxR,MaxC;
void SearchMaxArea(void); //搜索当前地图的最大区域
int BFSArea(int i,int j); //同色区域搜索，返回该区域的大小
void DelMaxArea(void); //删除最大区域
void RefreshMap(void); //刷新地图
int main(void)
{
int Game;
cin>>Game;
for(int g=1;g<=Game;g++)
{
for(int k=9;k>=0;k--)
cin>>map[k];
cout<<"Game "<
int step=0;
int RemainBalls=150;
int SumScore=0;
while(true)
{
MaxSize=-1;
SearchMaxArea();
if(MaxSize==0 || MaxSize==1)
break;
DelMaxArea();
RefreshMap();
int score=(MaxSize-2)*(MaxSize-2);
cout<<"Move "<<++step<<" at ("< cout<<"removed "<
RemainBalls-=MaxSize;
SumScore+=score;
}
if(RemainBalls==0)
SumScore+=1000;
cout<<"Final score: "< }
return 0;
}
/*搜索当前地图的最大区域*/
void SearchMaxArea(void)
{
memset(vist,false,sizeof(vist));
MaxSize=0;
for(int j=0;j<15;j++) //从左下角开始搜索
for(int i=0;i<10;i++)
{
int size=0;
if(!vist[i][j] && map[i][j])
{
size=BFSArea(i,j);
if(MaxSize {
MaxSize=size;
MaxR=i;
MaxC=j;
}
}
}
return;
}
/*同色区域搜索*/
int BFSArea(int i,int j)
{
class
{
public:
int x,y;
}queue[151];
int head,tail;
queue[head=tail=0].x=i;
queue[tail++].y=j;
vist[i][j]=true;
int size=0;
char color=map[i][j];
while(head {
int x=queue[head].x;
int y=queue[head++].y;
size++;
if(x+1<10 && !vist[x+1][y] && map[x+1][y]==color) //上
{
vist[x+1][y]=true;
queue[tail].x=x+1;
queue[tail++].y=y;
}
if(x-1>=0 && !vist[x-1][y] && map[x-1][y]==color) //下
{
vist[x-1][y]=true;
queue[tail].x=x-1;
queue[tail++].y=y;
}
if(y-1>=0 && !vist[x][y-1] && map[x][y-1]==color) //左
{
vist[x][y-1]=true;
queue[tail].x=x;
queue[tail++].y=y-1;
}
if(y+1<15 && !vist[x][y+1] && map[x][y+1]==color) //右
{
vist[x][y+1]=true;
queue[tail].x=x;
queue[tail++].y=y+1;
}
}
return size;
}
/*删除最大区域*/
void DelMaxArea(void)
{
class
{
public:
int x,y;
}queue[151];
int head,tail;
queue[head=tail=0].x=MaxR;
queue[tail++].y=MaxC;
MaxColor=map[MaxR][MaxC];
map[MaxR][MaxC]=0; //删除该格上的球
while(head {
int x=queue[head].x;
int y=queue[head++].y;
map[x][y]=0;
if(x+1<10 && map[x+1][y]==MaxColor) //上
{
map[x+1][y]=0;
queue[tail].x=x+1;
queue[tail++].y=y;
}
if(x-1>=0 && map[x-1][y]==MaxColor) //下
{
map[x-1][y]=0;
queue[tail].x=x-1;
queue[tail++].y=y;
}
if(y-1>=0 && map[x][y-1]==MaxColor) //左
{
map[x][y-1]=0;
queue[tail].x=x;
queue[tail++].y=y-1;
}
if(y+1<15 && map[x][y+1]==MaxColor) //右
{
map[x][y+1]=0;
queue[tail].x=x;
queue[tail++].y=y+1;
}
}
return;
}
/*刷新地图*/
void RefreshMap(void)
{
bool empty[15]={false};
int i,j;
/*处理从上到下的移动*/
for(j=0;j<15;j++)
{
bool flag=false; //标记第j列是否全列为空
int pi=-1;
for(i=0;i<10;i++)
{
if(map[i][j])
{
flag=true;
if(pi!=-1)
{
map[pi][j]=map[i][j];
map[i][j]=0;
i=pi;
pi=-1;
}
}
else
{
pi=i;
while(i+1<10 && !map[i+1][j])
i++;
}
}
if(!flag)
empty[j]=true; //第j列为空
}
/*处理从右到左的移动*/
int k=-1;
for(j=0;j<15;j++)
{
if(!empty[j])
{
if(k!=-1)
{
for(int x=0;x<10;x++)
{
map[x][k]=map[x][j];
map[x][j]=0;
}
empty[j]=true;
j=k;
k=-1;
}
}
else
{
k=j;
while(j+1<15 && empty[j+1])
j++;
}
}
return;
}