UVa 339 SameGame Simulation

题目描述单人游戏SameGame\texttt{SameGame}SameGame在一个MMM行NNN列的矩形网格上进行。每个格子中包含一个000到999之间的正整数。游戏的目标是移除网格中的所有数字。玩家通过重复选择一个格子进行消除来尝试达成目标。每次选择一个格子进行消除时包含该格子中相同数字的连通区域定义如下中的所有格子都会被移除然后被移除格子上方的格子向下掉落右侧的列向左滑动。当所有格子都被移除时游戏胜利或者当无法再移除任何格子时游戏结束。一个区域只有在包含至少两个格子时才能被移除。连通区域的定义从区域中的任何格子出发通过水平左/右和/或垂直上/下移动可以到达的所有格子且这些格子必须包含相同的数值。坐标系统格子从网格的左下角开始编号该格子为(1,1)(1,1)(1,1)。其上方的格子为(2,1)(2,1)(2,1)其右侧的格子为(1,2)(1,2)(1,2)。输入格式输入完全由非负整数组成不考虑行结构。每个网格和消除序列以MMM和NNN的值开始。如果其中任何一个值为000则输入结束。接下来是M×NM \times NM×N个网格整数按行主序给出即按(1,1),(1,2),…,(1,N),(2,1),…,(M,N)(1,1), (1,2), \dots, (1,N), (2,1), \dots, (M,N)(1,1),(1,2),…,(1,N),(2,1),…,(M,N)的顺序。网格数据之后是若干对整数每对表示被选择消除的格子的行和列。这个序列以一对0 0结束。如果游戏获胜程序必须跳过剩余的所有整数对包括0 0以读取下一个网格的数据。输出格式对于每个网格输出其编号从111开始。然后输出处理所有选择后剩余的网格或者消息Game Won。样例输入3 5 1 2 3 5 5 2 2 3 5 1 1 3 5 2 2 3 5 2 2 1 2 1 1 0 0 3 5 1 2 3 5 5 2 2 3 5 1 1 3 5 2 2 2 2 1 2 1 4 1 2 99 99 0 0 4 3 1 4 4 4 4 2 1 2 3 3 1 3 1 2 1 1 1 3 1 1 0 0 0 0样例输出Grid 1. Game Won Grid 2. 1 2 1 2 1 Grid 3. Game Won题目分析问题的本质这是一个网格消除游戏的模拟问题。核心操作包括连通区域检测使用洪水填充flood fill\texttt{flood fill}flood fill标记与选中格子同值且连通的区域区域移除将标记的格子设为−1-1−1表示空重力下落空位上方的格子向下掉落列左移全空的列向左滑动坐标系统注意题目中的坐标系统与通常的二维数组索引不同(1,1)(1,1)(1,1)是左下角(2,1)(2,1)(2,1)是(1,1)(1,1)(1,1)上方的格子行号从下到上递增在代码实现中通常使用grid[r][c]其中r1对应最下面一行rM对应最上面一行。这与输入顺序一致先输入第111行即最下面一行。消除条件一个选择是有效的当且仅当选中的格子存在1≤row≤M1 \leq row \leq M1≤row≤M1≤column≤N1 \leq column \leq N1≤column≤N选中的格子不是空的grid[row][column] 0选中的格子属于一个至少有两个格子的连通区域连通区域的判断可以通过检查上下左右四个方向是否有相同数值的格子。参考代码// SameGame Simulation// UVa ID: 339// Verdict: Accepted// Submission Date: 2016-07-06// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intM,N,grid[50][50],cases0;intoffset[4][2]{{0,1},{1,0},{0,-1},{-1,0}};// 洪水填充标记所有与 (row, column) 连通且值为 value 的格子voidfloodFill(introw,intcolumn,intvalue){if(row1rowMcolumn1columnN)if(grid[row][column]value){grid[row][column]-1;// 标记为已移除for(intk0;k4;k)floodFill(rowoffset[k][0],columnoffset[k][1],value);}}// 下落和左移调整voidadjust(){// 阶段1重力下落格子向下掉落for(intc1;cN;c){intlow1;// 找到第一个空位while(lowMgrid[low][c]0)low;if(lowM1)continue;// 该列已满// 将非空格子向下移动for(intuplow1;upM;up)if(grid[up][c]0){grid[low][c]grid[up][c];grid[up][c]-1;low;}}// 阶段2空列左移intmovedColumn0;for(intcN;c1;c--){// 检查当前列是否为空boolemptyColumntrue;for(intr1;rM;r)if(grid[r][c]0){emptyColumnfalse;break;}if(emptyColumnfalse)continue;// 将右侧列向左移动for(intr1;rM;r){for(intemptyCc;emptyCN-movedColumn;emptyC)grid[r][emptyC]grid[r][emptyC1];}// 清空最右侧的列for(intr1;rM;r)grid[r][N-movedColumn]-1;movedColumn;}}// 输出当前网格从顶部行开始voiddisplay(){for(intrM;r1;r--){for(intc1;cN;c)cout grid[r][c];coutendl;}}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);while(cinMN,MN){// 读取网格从底部行开始for(intr1;rM;r)for(intc1;cN;c)cingrid[r][c];introw,column;while(cinrowcolumn,rowcolumn){// 检查选择是否有效if(row0||rowM||column0||columnN)continue;if(grid[row][column]-1)continue;// 检查是否有相邻的同值格子区域大小 ≥ 2boollinkedfalse;for(intk0;k4;k){intnextRowrowoffset[k][0],nextColumncolumnoffset[k][1];if(nextRow1||nextRowM||nextColumn1||nextColumnN)continue;if(grid[nextRow][nextColumn]grid[row][column]){linkedtrue;break;}}if(linkedfalse)continue;// 执行消除floodFill(row,column,grid[row][column]);adjust();}// 输出结果if(cases)coutendl;coutGrid cases.endl;// 检查是否获胜intcell0;for(intr1;rM;r)for(intc1;cN;c)if(grid[r][c]0)cell;if(cell0)cout Game Wonendl;else{// 输出剩余网格for(intrM;r1;r--){cout ;for(intc1;cN;c)if(grid[r][c]0)cout grid[r][c];elsecout ;coutendl;}}}return0;}