题目描述
“Same\texttt{Same}Same” 是一种单人游戏，棋盘为101010行151515列，每个格子包含红色（R）、绿色（G）或蓝色（B）的球。两个球属于同一簇当且仅当它们颜色相同，且可以通过上下左右四个方向经过同色球互相到达。每步操作中，玩家选择一个至少包含两个球的簇，将该簇中所有球从棋盘上移除。随后棋盘按两步压缩：
步骤1\texttt{1}1. 每列中剩余的球向下移动以填补空位，各列内球的顺序保持不变。
步骤2\texttt{2}2. 若有整列为空，则将左侧所有剩余列向左平移，列的顺序保持不变。
游戏目标是移除棋盘上所有球，当所有球被移除或所有簇大小均为111时游戏结束。得分规则：初始得分为000，移除一个包含mmm个球的簇时，得分增加(m−2)2(m - 2)^2(m−2)2。若最终所有球被移除，额外奖励100010001000分。
本题要求模拟一种贪心策略：每步选择能形成最大簇的球，若有多个最大簇，选择最靠左的；若仍有并列，则选择这些球中最靠下的。输出每步移除的详细信息以及最终得分。
输入格式
第一行为正整数NNN，表示游戏局数。随后每局游戏由101010行组成，每行包含151515个字符，字符为'R'、'G'或'B'，表示棋盘从上到下的每一行，从左到右排列。每局游戏之前有一个空行。
输出格式
对于每局游戏，首先输出Game k:并换行。然后按顺序输出每一步的信息，格式为：
Move x at (r,c): removed b balls of color C, got s points.其中xxx为步数编号（从111开始），rrr和ccc分别为所选球的行号和列号（行号从底部111到顶部101010，列号从左111到右151515），bbb为移除的球数，CCC为颜色字符，sss为该步得分（不含最终100010001000分奖励）。若游戏结束（所有球被移除或仅剩单球簇），输出：
Final score: s, with b balls remaining.每局游戏输出后跟一个空行。注意复数形式balls和points即使在数值为111时也使用。
样例输入
3 RGBGBGRBRRGBGB RGBGRBGRBGRGBRG BRRRGBBRGRGBBB GGRGBGBGRRGGGB GGBGRRRRRBGBRRR BBBBBBBBBBBBB BBBBBBBBBBBBB RRRRRRRRRRRRRR RRRRRRGGGRRRRR GGGGGGGGGGGGGG RRRRRRRRRRRRRR RRRRRRRRRRRRRR GGGGGGGGGGGGGGG GGGGGGGGGGGGGGG BBBBBBBBBBBBB BBBBBBBBBBBBB RRRRRRRRRRRRRRR RRRRRRRRRRRRRR GGGGGGGGGGGGGGG GGGGGGGGGGGGGGG RBGRBGRBGRBGRBG BGRBGRBGRBGRBGR GRBGRBGRBGRBGRB RBGRBGRBGRBGRBGR GRBGRBGRBGRBGRB RGRBGRBGRBGRBGRB BGRBGRBGRBGRBGR GRBGRBGRBGRBGRB RBGRBGRBGRBGRB样例输出
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.题目分析
该问题要求严格按照贪心策略模拟游戏过程。每步需找到当前棋盘上最大的同色连通簇（四连通），若多个簇大小相同，选择列号最小的（即最左），若列号仍相同，选择行号最小的（即最底部）。移除该簇后，进行压缩（列内下移，空列左移），然后继续下一轮。当最大簇大小为111或棋盘上球数为000时游戏结束。棋盘尺寸固定为10×1510 \times 1510×15，球数最多150150150，每次移除和压缩操作规模小，直接模拟即可。
解题思路
采用递归Flood fill\texttt{Flood fill}Flood fill统计簇大小并标记访问。每轮扫描棋盘，按列从左到右、行从底到顶的顺序遍历，遇到未访问的非空格，使用floodFill\texttt{floodFill}floodFill统计簇大小，记录最大簇及其位置（行、列）。由于扫描顺序就是列优先、行从底到顶，当遇到更大的簇时更新，相等的簇不更新，因此自然满足“最左、最底”的贪心选择。
选定簇后，使用remove\texttt{remove}remove函数将该簇全部标记为'0'（空），然后调用compress\texttt{compress}compress进行压缩。压缩时，先将每列中非空球从底部向上填入临时数组，然后按从左到右的顺序将非空列依次放置，形成压缩后的棋盘。最后累加得分，若移除球数为mmm，则得分为(m−2)2(m-2)^2(m−2)2，并减少剩余球数。当剩余球数为000或最大簇大小为111时停止循环，若剩余球数为000则额外加100010001000分。输出每一步信息及最终得分。
算法时间复杂度O(步数×10×15)O(\text{步数} \times 10 \times 15)O(步数×10×15)，每步最大150150150步，棋盘仅150150150格，效率极高。
代码实现
// The Same Game// UVa ID: 758// Verdict: Accepted// Submission Date: 2017-10-22// UVa Run Time: 0.060s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;charmaze[10][15],shadow[10][15];intvisited[10][15],offset[4][2]={{0,1},{0,-1},{1,0},{-1,0}};voidfloodFill(inti,intj,charold,int&cnt){if(i>=0&&i<=9&&j>=0&&j<=14&&!visited[i][j]&&maze[i][j]==old){cnt++;visited[i][j]=1;for(intk=0;k<4;k++)floodFill(i+offset[k][0],j+offset[k][1],old,cnt);}}voidremove(inti,intj,charold,charreplaced){if(i>=0&&i<=9&&j>=0&&j<=14&&maze[i][j]==old){maze[i][j]=replaced;for(intk=0;k<4;k++)remove(i+offset[k][0],j+offset[k][1],old,replaced);}}voidcompress(){memset(shadow,'0',sizeof(shadow));for(inti=0,x=0;i<15;i++){inty=9;for(intj=9;j>=0;j--){if(maze[j][i]!='0'){shadow[y][x]=maze[j][i];y--;}}if(y!=9)x++;}memcpy(maze,shadow,sizeof(shadow));}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0;cin>>cases;for(intc=1;c<=cases;c++){if(c>1)cout<<'\n';cout<<"Game "<<c<<":\n\n";for(inti=0;i<10;i++)for(intj=0;j<15;j++)cin>>maze[i][j];intballs=150,score=0,step=1;while(true){memset(visited,0,sizeof(visited));intremoved=0,row=-1,column=-1;for(inti=0;i<15;i++)for(intj=9;j>=0;j--){if(visited[j][i]||maze[j][i]=='0')continue;intcnt=0;floodFill(j,i,maze[j][i],cnt);if(removed<cnt)removed=cnt,row=j,column=i;}if(removed==1)break;cout<<"Move "<<step++;cout<<" at ("<<(10-row)<<','<<(column+1);cout<<"): removed "<<removed<<" balls of color ";cout<<maze[row][column]<<", got ";cout<<(removed-2)*(removed-2)<<" points.\n";balls-=removed;score+=(removed-2)*(removed-2);if(balls==0)break;remove(row,column,maze[row][column],'0');compress();}if(balls==0)score+=1000;cout<<"Final score: "<<score<<", with "<<balls<<" balls remaining.\n";}return0;}总结
本题模拟固定规则的消除游戏，核心在于正确实现簇的统计和棋盘压缩。通过Flood fill\texttt{Flood fill}Flood fill寻找最大簇，利用列优先、行从底到顶的扫描顺序自然满足贪心选择条件。压缩分为列内下移和空列左移两步，使用临时数组可简洁实现。输出格式需注意坐标转换（行号从底部计起）和复数形式。该解法直接且高效，适用于固定大小的棋盘，是模拟类题目的典型范例。
