题目描述“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到右151515bbb为移除的球数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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;charmaze[10][15],shadow[10][15];intvisited[10][15],offset[4][2]{{0,1},{0,-1},{1,0},{-1,0}};voidfloodFill(inti,intj,charold,intcnt){if(i0i9j0j14!visited[i][j]maze[i][j]old){cnt;visited[i][j]1;for(intk0;k4;k)floodFill(ioffset[k][0],joffset[k][1],old,cnt);}}voidremove(inti,intj,charold,charreplaced){if(i0i9j0j14maze[i][j]old){maze[i][j]replaced;for(intk0;k4;k)remove(ioffset[k][0],joffset[k][1],old,replaced);}}voidcompress(){memset(shadow,0,sizeof(shadow));for(inti0,x0;i15;i){inty9;for(intj9;j0;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);intcases0;cincases;for(intc1;ccases;c){if(c1)cout\n;coutGame c:\n\n;for(inti0;i10;i)for(intj0;j15;j)cinmaze[i][j];intballs150,score0,step1;while(true){memset(visited,0,sizeof(visited));intremoved0,row-1,column-1;for(inti0;i15;i)for(intj9;j0;j--){if(visited[j][i]||maze[j][i]0)continue;intcnt0;floodFill(j,i,maze[j][i],cnt);if(removedcnt)removedcnt,rowj,columni;}if(removed1)break;coutMove step;cout at ((10-row),(column1);cout): removed removed balls of color ;coutmaze[row][column], got ;cout(removed-2)*(removed-2) points.\n;balls-removed;score(removed-2)*(removed-2);if(balls0)break;remove(row,column,maze[row][column],0);compress();}if(balls0)score1000;coutFinal score: score, with balls balls remaining.\n;}return0;}总结本题模拟固定规则的消除游戏核心在于正确实现簇的统计和棋盘压缩。通过Flood fill\texttt{Flood fill}Flood fill寻找最大簇利用列优先、行从底到顶的扫描顺序自然满足贪心选择条件。压缩分为列内下移和空列左移两步使用临时数组可简洁实现。输出格式需注意坐标转换行号从底部计起和复数形式。该解法直接且高效适用于固定大小的棋盘是模拟类题目的典型范例。