1.任务：

[问题描述]

建立一个10*20的矩形方格图，其中有10种不同的图案，每种图案个数为偶数，填满矩形方格图。

[基本要求]

（1）随机产生原始数据；

（2）输入两个位置，如果两者图案相同，并且可以用小于等于3条直线相连，即可消除该两个图案。

2.采用的数据结构

        采用图

3.算法设计思想

        利用rand函数随机生成底图，通过JudgeLine和JudgeCol函数来判断在同一直线上的两点之间是否可连，即两点之间是否还有其他元素存在。对于选中的两个位置上的元素是否可消进行判断，在两位置上的元素相同的情况下，倘若两位置相邻则可消，依次分析可以用一根线、两根线和三根线消除的情况，对以消除的元素位置进行标记，并且在图上消失。每成功消除一对元素计分，增加趣味性。时间复杂度T(n)=O(n).

4.源程序：

#include <iostream>
#include <cstdlib>
#include <process.h>
#include <math.h>
#include <ctime>
using namespace std; void CreateGraph(int a[10][20])                 //随机生成底图 
{srand((int)time(0));int n=95;for(int i=0;i<9;i++){int num;num=rand()%(n-(10-i)*8)+8;for(int j=0;j<num*2;j++){int x,y;x=rand()%10;y=rand()%20;if(a[x][y]==-1){a[x][y]=i;}else{j--;}}n=n-num;}for(int i=0;i<10;i++){for(int j=0;j<20;j++){if(a[i][j]==-1){a[i][j]=9;}}}
}int JudgeLine(int a[10][20],int x1,int x2,int y)       //判断（x1，y）（x2，y）之间是否可连
{if(x1>x2)                                          //保证 x1<=x2{int t;t=x2;x2=x1;x1=t;}if((x2-x1)==1){return 1;}for(int i=x1+1;i<x2;i++){if(a[i][y]!=-1){return 0;}}return 1;
} int JudgeCol(int a[10][20],int x,int y1,int y2)      //判断（x，y1）（x，y2）之间是否可连
{if(y1>y2)                                        //保证 y1<=y2{int t;t=y2;y2=y1;y1=t;}if((y2-y1)==1){return 1;}for(int i=y1+1;i<y2;i++){if(a[x][i]!=-1){return 0;}}return 1;
} int action(int a[10][20],int x1,int y1,int x2,int y2,int score)
{if((a[x1][y1]!=a[x2][y2]) || ((x1==x2)&&(y1==y2))){printf("输入位置不满足条件，请重试！\n");return 0;}else{if((abs(x1-x2)==1) || (abs(y1-y2)==1))     //（x1,y1）（x2,y2）相邻时，消除 {printf("消除成功!\n"); return 1;}else{if(x1>x2)                            //使得（x1,y1）始终在（x2,y2）左侧 {int t;t=x2;x2=x1;x1=t;t=y2;y2=y1;y1=t;}if(x1==x2)                          //判断是否可以用一根线消除 {if(JudgeLine(a,x1,y1,y2)==1){printf("消除成功!\n"); return 1;}}if(y1==y2){if(JudgeCol(a,x1,x2,y2)==1){printf("消除成功!\n"); return 1;} }int flag1,flag2;                    //判断是否可以用两条线相连 flag1=JudgeLine(a,x1,x2,y2);flag2=JudgeCol(a,x1,y1,y2);if(flag1&&flag2&&(a[x1][y2]==-1)){printf("消除成功!\n");return 1;} flag1=JudgeLine(a,x1,x2,y1);flag2=JudgeCol(a,x2,y1,y2);if(flag1&&flag2&&(a[x2][y1]==-1)){printf("消除成功!\n"); return 1;} for(int i=0;i<10;i++)              //判断是否可以用三条线消除 {if(a[x1][i]==-1 && JudgeCol(a,x1,y1,i)==1){if(a[x2][i]==-1 && JudgeCol(a,x2,y2,i)==1){if(JudgeLine(a,x1,x2,i)==1){printf("消除成功!\n"); return 1;}}}}for(int i=0;i<20;i++){if(a[i][y1]==-1 && JudgeLine(a,x1,i,y1)==1){if(a[i][y2]==-1 && JudgeLine(a,x2,i,y2)==1){if(JudgeCol(a,i,y1,y2)==1){printf("消除成功!\n"); return 1;}}}}}}printf("消除失败！");return 0;
}int main() 
{printf("\n---------------------------欢迎来到连连看小程序！------------------------\n");printf("\t\t\t\t\t\t\t\t\t总得分：0\n"); int a[10][20];for(int i=0;i<10;i++){for(int j=0;j<20;j++){a[i][j]=-1;}}CreateGraph(a);int flag,x1,x2,y1,y2;int score=0;while(1){system ("cls");printf("\n---------------------------欢迎来到连连看小程序！------------------------\n");printf("\t\t\t\t\t\t\t\t\t总得分：%d\n",score); printf("当前地图为：\n\n");printf("        ");for(int i=0;i<20;i++){printf("%d ",(i+1)%10);}printf("\n        _______________________________________\n\n");for(int i=0;i<10;i++){printf("  %d  |  ",(i+1)%10);for(int j=0;j<20;j++){if(a[i][j]==-1){printf("  ");}else{printf("%d ",a[i][j]);}}printf(" |  %d\n",(i+1)%10);    }printf("        _______________________________________\n\n");printf("        ");for(int i=0;i<20;i++){printf("%d ",(i+1)%10);}printf("\n\n");printf("请输入想消除的方块位置，\n(例：选择第1行第1列和第4行第2列，即输入：1 1 4 2)\n");fflush(stdin);scanf("%d %d %d %d",&x1,&y1,&x2,&y2);x1--;x2--;y1--;y2--;int success;success=action(a,x1,y1,x2,y2,score);system("pause");if(success==1){a[x1][y1]=-1;a[x2][y2]=-1;score++;continue;}}return 0;
}

5.源程序测试数据及结果

连连看测试数据

连连看测试结果

6.存在问题及改进方法

        在连连看的算法实现的方案中，使用了枚举法，对于所有可能出现的可消除的情况都进行了一一列举，可能出现重复，略显累赘。可以加深思考，如何将其中的几种情况进行合并，使算法更加简洁明了。