连连看游戏连连看游戏是一个在10 \Theta 15 的板子上玩的单人游戏。每个方块里都有一个红球，绿球或者蓝球。两个同颜色的球属于同一串，每一个球都能被它周围上下左右四个方位同颜色的球够着（即属于同一串）。在游戏的每一个阶段中，游戏者选择一个球，这个球所属的串至少包含两个球，然后在木板上移走该串球。然后这个木板在经过以下两个阶段后被“压缩”。
1，把每一列中剩下的球往下移动以填补空位。球的排列顺序被保留。
2，如果某列中球全被拿走了，把其右边的球整列整列地尽量往左移。球的排列顺序被保留。
在下面的例子里我们选择左下角的球：(很可惜,图象传不上来)
游戏的目的是把所有的球从木板中移走，当所有的球都被移走或者每串球只剩一个的时候游戏就算结束了。每次游戏分数的计算如下：玩家开始分数为0，每移走含m个球一串球，玩家分数增加 (m-2)^2分。如果在游戏结束时所有的球都被移走，玩家将得到额外的1000分的奖励。
你猜想最好的策略可能是每次都选择拥有最大串的球，那么你要做的就是编一个程序模拟用这种策略来玩这个游戏。如果有两个或以上的球可以选择，程序将选择最左边的球来得到最大串。如果仍然有同时满足条件的，将优先选择最底端的球。
输入：
输入游戏中球最初的排列，即所谓迷宫的分布。每一行包括MaxLine个字母，每一个字母为“R”，“G”或“B”，明确给出各行各列的球的颜色，共MaxRow行。
输出：
关于每次移动的信息，和每次移动所得到的分数，每次移动的输出按照如下格式：Move x at (r,c): removed b balls of color C, got s points，其中x是移动的次序数，r和c表示被选中的球所在的行数和列数。行数从下往上数1-MaxRow总共是MaxRow行，列数从左往右数1-MaxLin总共MaxLin行。b表示被移走的那串球的个数；C表示球的颜色，可以是“R”，“G”或“B”；s是移动所得的分数。这个分数并不包括因把球全部移走而得到的额外奖励。最后的分数必须象这样公布：Final score: s, with b balls remaining. 在每一次游戏分数公布间插入一空行，使用复数形式输出 "balls"和"points" ，即便只有一个球也不例外。
算法思路：1 输入数据，建立迷宫。2 复制一个迷宫，按从左到右，从下到上的顺序走迷宫，把所有的路径都存储入队列；按照不同的路径建立多个队列。3 比较队列的长度，去掉最长的一个队列中的元素。并输出相应的分数和信息。4 重新排列迷宫，空白处元素值为0或空格。5判断是否满足游戏结束条件，若是，输出最后结果；否则返回步骤2。Sample Input RGGBBGGRBRRGGBG RBGRBGRBGRBGRBGRRRRGBBBRGGRBBBGGRGBGGBRRGGGBGGBGGRRRRRBGGRRRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRRRRRRRGGGGRRRRRGGGGGGGGGGGGGGGSample Output 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. 原代码如下：#include <stdio.h>#include <stdlib.h>#define MaxLine 6#define MaxRow 5 typedef struct{ //存储坐标 int x; int y;} pos;typedef struct mg{ //用队列表示迷宫路径，即所有相邻的同色球的坐标集合 pos array[MaxLine*MaxRow]; int front; int rear; char col; //球的颜色 } Queue; void Build(char MG_S[][MaxLine+2]); //建立迷宫（外围建筑围墙）void Copy(char MG_S[][MaxLine+2], char MG[][MaxLine+2]); //把原始迷宫复制到待测迷宫中int Solve(char MG[][MaxLine+2], Queue que[]); //用队列存储所有相邻的同色球的坐标集合，返回队列的个数 Queue MGSS(char MG[][MaxLine+2], Queue que, char color);//依次搜索每一个球的周围，把所有同色球入列 int Choose(Queue que[], int len);//选择最长的队列，并返回其序号int Print(Queue q, int num, char color, long *score);//输出分数及相关信息void PrintEnd(char MG_S[][MaxLine+2], long score); //输出最后得分 void Remove(char MG_S[][MaxLine+2], Queue q);//移走该串球 void Move(char MG_S[][MaxLine+2]);//对剩余球进行重新排列 int JudgeLine(char MG_S[][MaxLine+2], int line);//判断该列球是否全部被移走 int main(int argc, char *argv[]){ char MG_S[MaxRow+2][MaxLine+2], MG[MaxRow+2][MaxLine+2]; //用来存储初始迷宫和复制的迷宫 Queue que[MaxLine*MaxRow]; //队列 long score=0; //玩家的分数 int NumberOfQueue, max;//分别表示队列的个数和最长的队列的序号 int NumberOfChoose=0;//移除的次数,即报分的次数 int i, j; Build(MG_S);//建立迷宫 b: Copy(MG_S, MG); //复制迷宫 NumberOfQueue = Solve(MG, que);//用队列存储所有相邻的同色球的坐标集合，返回队列的个数 //printf("\nNumberOfQueuet=%d\n",NumberOfQueue); max = Choose(que, NumberOfQueue);//选择最长的队列，并返回其序号 //printf("\nmax=%d,len=%d\n",max,que[max].rear+1); system("PAUSE"); if(NumberOfQueue && (que[max].rear >= 1))//如果该串球的个数大于1，执行移除操作 { NumberOfChoose = Print(que[max], NumberOfChoose, que[max].col, &score);//输出分数及相关信息 Remove(MG_S, que[max]);//移走该串球 /* for(i=0; i<=MaxRow+1; i++) //把原始迷宫复制到待测迷宫中 { for(j=0; j<=MaxLine+1; j++) printf("%c", MG_S[i][j]); printf("\n"); } printf("\n"); */ Move(MG_S);//对剩余球进行重新排列 /* for(i=0; i<=MaxRow+1; i++) //把原始迷宫复制到待测迷宫中 { for(j=0; j<=MaxLine+1; j++) printf("%c", MG_S[i][j]); printf("\n"); } */ goto b; } else { /* for(i=0; i<=MaxRow+1; i++) //把原始迷宫复制到待测迷宫中 { for(j=0; j<=MaxLine+1; j++) printf("%c", MG_S[i][j]); printf("\n"); } */ PrintEnd(MG_S, score); //输出最后得分 } system("PAUSE"); return 0;} void Build(char MG_S[][MaxLine+2]) //建立迷宫（外围建筑围墙）{ int i, j, flag; puts("建立迷宫："); for(i=1; i<=MaxRow; i++) { for(j=1; j<=MaxLine ; j++) scanf("%c", &MG_S[i][j]); fflush(stdin); } for(i=0; i<=MaxRow+1; i++) /*外围建筑围墙*/ { MG_S[i][0] = '*'; MG_S[i][MaxLine+1] = '*'; } for(j=0; j<=MaxLine+1; j++) /*外围建筑围墙*/ { MG_S[0][j] = '*'; MG_S[MaxRow+1][j] = '*'; } } void Copy(char MG_S[][MaxLine+2], char MG[][MaxLine+2]) //把原始迷宫复制到待测迷宫中{ int i, j; for(i=0; i<=MaxRow+1; i++) //把原始迷宫复制到待测迷宫中 for(j=0; j<=MaxLine+1; j++) MG[i][j] = MG_S[i][j]; for(i=0; i<=MaxRow+1; i++) //把原始迷宫复制到待测迷宫中 { for(j=0; j<=MaxLine+1; j++) printf("%c", MG[i][j]); printf("\n"); }} int Solve(char MG[][MaxLine+2], Queue que[]) //用队列存储所有相邻的同色球的坐标集合，返回队列的个数 { int row, line; int count=0; for(line=1; line<=MaxLine; line++)//从左下角开始搜索 for(row=MaxRow; row>=1; row--) { if( MG[row][line] != '*') //如果该位置未被搜索，将其存入新的队列 { que[count].front = que[count].rear = 0;//存储该队列的第一个元素 que[count].array[que[count].front].x = row; que[count].array[que[count].front].y = line; que[count].col = MG[row][line]; MG[row][line] = '*';//已搜索过的位置用'*'表示 que[count] = MGSS(MG, que[count], que[count].col); //存储该队列的其他元素 count++; } } return count;}Queue MGSS(char MG[][MaxLine+2], Queue que, char color)//依次搜索每一个球的周围，把所有同色球入列 { int PosX[4]={0,1,0,-1};//X坐标中东南西北四个方位的表示 int PosY[4]={1,0,-1,0};//Y坐标中东南西北四个方位的表示 int nx, ny; //表示该球的当前坐标 int row, line;//表示被搜索的位置的坐标 int fx;//表示搜索的方向,依次为东南西北 int i; while(que.front <= que.rear) //依次搜索每一个球的周围，把所有同色球入列 { nx = que.array[que.front].x; ny = que.array[que.front].y; for(fx=0; fx<4; fx++) //搜索该球四周的位置 { row = nx + PosX[fx]; line = ny + PosY[fx]; if(MG[row][line]==color) //把所有同色球入列 { que.rear++; que.array[que.rear].x = row; que.array[que.rear].y = line; MG[row][line] = '*'; } } que.front++; } return que; //返回该结构变量 } int Choose(Queue que[], int len)//选择最长的队列，并返回其序号{ int i, max=0; for(i=1; i<len; i++) if(que[max].rear < que[i].rear) max = i; return max;}int Print(Queue q, int num, char color, long *score)//输出分数及相关信息{ *score += (q.rear-1)*(q.rear-1); printf("Move %d at (%d,%d):", ++num, q.array[0].x, q.array[0].y); printf("removed %d balls of color %c, got %ld points.\n", q.rear+1, color, *score); return num;//返回移动得分的次数 }void PrintEnd(char MG_S[][MaxLine+2], long score) //输出最后得分 { int row, line; int count=0;//存储剩余球的个数 for(line=1; line<=MaxLine; line++)//从左下角开始搜索 for(row=MaxRow; row>=1; row--) if(MG_S[row][line] != '*') count++; //累计剩余球的个数 if(count == 0) score += 1000; printf("Final score: %d, with %d balls remaining.\n", score, count); } void Remove(char MG_S[][MaxLine+2], Queue q)//移走该串球 { int i; for(i=0; i<=q.rear; i++) //把原始迷宫复制到待测迷宫中 MG_S[q.array[i].x][q.array[i].y] = '*'; } void Move(char MG_S[][MaxLine+2])//对剩余球进行重新排列 { int row, line; int k; for(line=1; line<=MaxLine; line++)//从左下角开始搜索，把每一列中剩下的球往下移动以填补空位 { k = 0; for(row=MaxRow; row>=1; row--) { if(MG_S[row][line] == '*') //不是一个一个地移动，而是一串一串地移动 ，效率较高 k++; else { MG_S[row+k][line] = MG_S[row][line]; if(k != 0) MG_S[row][line] = '*'; } } } k = 0; for(line=1; line<=MaxLine; line++) { if(JudgeLine(MG_S, line))//如果该列球全部被移走 k++; else for(row=MaxRow; row>=1; row--)//把右边的球往左边移 { MG_S[row][line-k] = MG_S[row][line]; if(k != 0) MG_S[row][line] = '*'; } }}int JudgeLine(char MG_S[][MaxLine+2], int line)//判断该列球是否全部被移走 { int row; for(row=MaxRow; row>=1; row--) if(MG_S[row][line] != '*') return 0; return 1;}正文
连连看游戏2005-12-22 11:11:00
【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/goal00001111/8676.html
阅读(7201) | 评论(0)
版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！
评论