ACM题目分析与解答POJThe same game

1、The same game 解题报告00001097 吴明辉1The same game 解题报告题目重述算法设计主要数据实现优化2The same game 题目重述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 on

2、e 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 step

3、s: 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 thebott

4、om left corner in the sub-board below causes: 3The same game 题目重述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. Whe

5、n a cluster of m balls is removed, the players 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 b

6、y 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. 4The same game 算法设计这是一道模拟类的题

7、目需要存储的如果按照题目所说的完整的步骤模拟共分为以下几步：1.对于每一个点进行图的遍历，统计所在的cluster的大小。2.选出最大的cluster，把它move掉3.按照题目所说进行压缩5The same game 主要数据根据算法要求需要存储的数据有1.char map1015 用来存储每一个点的颜色属性2.bool visit1015 用来存储每一个点在图的遍历时的访问状态3.int cluster1015 用来存储每一个点所在的cluster的大小6The same game 程序实现图的遍历void visitall(int x,int y)visitxy=1;sum+;if(x0

8、&mapx-1y=mapxy&visitx-1y=0)visitall(x-1,y);if(y0&mapxy-1=mapxy&visitxy-1=0)visitall(x,y-1);if(x9&mapx+1y=mapxy&visitx+1y=0)visitall(x+1,y);if(y14&mapxy+1=mapxy&visitxy+1=0)visitall(x,y+1);递归结束后全局变量sum的值为(x,y)所在cluster的大小7The same game 程序实现选出最大的clusterfor(j=0;j15;j+)for(i=0;iclusterxy)x=i;y=j;8The sa

9、me game 程序实现移除选定的cluster 并且压缩cal(x,y);for(i=0;i10;i+)for(j=0;j15;j+)if(visitij=1)mapij=0;for(i=0;i15;i+)for(j=0;j9;j+)for(k=j+1;k10;k+)if(mapji!=0)break;if(mapki!=0)mapji=mapki;mapki=0;break;9The same game 程序实现for(i=0;i14;i+) if(map0i!=0)continue;for(j=i+1;j15;j+)if(map0j!=0)for(k=0;k10;k+)mapki=map

10、kj;mapkj=0;break;10The same game 程序优化1.不是所有的点都要进行图的遍历2.如果一边遍历一边比较大小，则可以不需要数组cluster1015;3.压缩算法优化11The same game 程序优化pair maxpair()int x=0,y=0,i,j;tempcluster=0;pair temp;for(i=0;i10;i+)for(j=0;j15;j+)visitij=0;for(j=0;j15;j+)for(i=0;itempcluster)x=i;y=j;tempcluster=sum;temp.first=x;temp.second=y;return temp;12The same game 程序优化for (k=0, j=0; k15; k+) u=0; v=0; while (v=9) while