// 我真诚地保证：
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
// 数据结构与算法实习之连连看（自动消解）
// 文件名：Lianliankan.cpp
// 作者：-------
// 日期：2012年11月18日
// 编译环境：Microsoft Visual C++ 6.0
// 操作系统：Microsoft Windows XP
// 输入方式：键盘读入数据或文件读入数据皆可
// 输出方式：Graphics图形界面输出
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstring>
#include<ctime>
#include<vector>
#include<algorithm>
#include<graphics.h> // 需要先安装提交包内的EasyX库才能使用graphics.h
#include<windows.h>
#pragma comment(lib,"winmm.lib")
#define MAX_SIZE 22 // 数字矩阵行、列的最大值
#define MAX_WIDTH 20 // 列的最大值（不含最左和最右空出的列）
#define MAX_HEIGHT 12 // 行的最大值（不含最上和最下空出的行）
#define PATTERN_NUM 30 // 不同的图案的个数
#define SCREEN_WIDTH 120 // 屏幕宽度
#define SCREEN_HEIGHT 50 // 屏幕高度
#define WINDOW_WIDTH 119 // 窗口宽度
#define WINDOW_HEIGHT 30 // 窗口高度
#define MAX_MEM_SIZE 150
#define SLEEPTIME 240
#define MAX_SEARCH_TIME 13000
using namespace std;
// POS表示某一点，其中x代表行号，y代表列号
class POS
{
public:
int x,y;
POS(const int X=-1,const int Y=-1)
{
x=X;
y=Y;
}
};
// WAY表示点p1和点p2的一种消解方式，当t2为真时表示有两个拐角，分别用turn1和turn2表示，当t2为假而t1为真时表示有一个拐角，用turn1表示
class WAY
{
public:
POS p1,p2,turn1,turn2;
bool t1,t2;
WAY(){};
WAY(const int X1,const int Y1,const int X2,const int Y2,const bool T1=0,const bool T2=0)
{
p1.x=X1;
p1.y=Y1;
p2.x=X2;
p2.y=Y2;
t1=T1;
t2=T2;
}
int distance() // 计算连接p1和p2的最短折线长度
{
if(p1.x>p2.x)
{
if(p1.y>p2.y)return p1.x+p1.y-p2.x-p2.y;
else return p1.x+p2.y-p2.x-p1.y;
}
else
{
if(p1.y>p2.y)return p2.x+p1.y-p1.x-p2.y;
else return p2.x+p2.y-p1.x-p1.y;
}
}
};
// MEMDATA记录递归时已经搜索过的数据
class MEMDATA
{
public:
int pattern[MAX_SIZE][MAX_SIZE];
int patternnum[PATTERN_NUM+1];
int maxstep;
MEMDATA(const int p[][MAX_SIZE],const int pn[],const int M)
{
int i,j;
for(i=0;i<MAX_SIZE;i++)
for(j=0;j<MAX_SIZE;j++)
pattern[i][j]=p[i][j];
for(i=1;i<=PATTERN_NUM;i++)
patternnum[i]=pn[i];
maxstep=M;
}
};
static HMIDIOUT handle; // 音频输出句柄
static int pattern[MAX_SIZE][MAX_SIZE],weight[MAX_SIZE][MAX_SIZE]; // pattern为每个点的图案，weight为每个点的权值
static vector<WAY> vway,eway,answay; // vway记录当前的消解方法，eway记录从某点出发的消解路径，answay为使剩下图案最少的消解方法
// 以下为准备工作的函数
void init(); // 初始化界面、图案
bool input(int&,int[],int&,int&); // 选择输入模式、输入图案
int datacreate(int[],int,int); // 当选择自动生成图案时，自动生成一种图案方案
// 以下为计算部分的函数
void searchpos(int,int,int,int); // 从某一点出发，寻找能消解的点对
bool cmp(const WAY &w1,const WAY &w2); // 比较两种消解方式的权值
bool calculate(int,int,int,time_t); // 找能消解的点对并选择最佳方案消解
// 以下为输出的函数
void logoutput(int,int); // 将消解过程输出到log.txt中
void play(unsigned char); // 发出声音
void fillrectangle(int,int,int,int,COLORREF); // 画填充矩形
void drawline(int,int,int,int,COLORREF); // 画直线
void drawcircle(int,int,COLORREF); // 画填充圆
void turntoempty(int,int,int,int,COLORREF); // 将某块的颜色消掉
void drawdefaultimage(int,int,int); // 输出默认图案（当找不到图片文件时）
void graphicsoutput(int,int); // 图形界面输出（该函数在main函数中调用，再调用以上各函数）
void init()
{
HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTitle("连连看 Lianliankan");
COORD size={SCREEN_WIDTH,SCREEN_HEIGHT};
SetConsoleScreenBufferSize(hOut,size);
SMALL_RECT rc={0,0,WINDOW_WIDTH,WINDOW_HEIGHT};
SetConsoleWindowInfo(hOut,true,&rc);
unsigned long result=midiOutOpen(&handle,0,0,0,CALLBACK_NULL);
int i,j;
for(i=0;i<MAX_SIZE;i++)
for(j=0;j<MAX_SIZE;j++)
pattern[i][j]=0;
srand(unsigned(time(0)));
}
bool input(int &patternednum,int patternnum[],int &r,int &c)
{
int i,j,mode;
cout<<"请选择模式（输入1、2或3）：\n1：从键盘读入数据； 2：从文件读入数据； 3：自动生成数据\n";
cin>>mode;
if(mode<1||mode>3)
{
cout<<"出错！\n";
return 0;
}
cout<<endl;
if(mode==1||mode==2)
{
cout<<"数据样例：\n\n";
cout<<"┌———————————————————┐\n";
cout<<"︱ 8 12 ︱\n";
cout<<"︱ 15 10 9 10 2 5 25 22 16 6 8 11 ︱\n";
cout<<"︱ 23 21 21 20 21 25 14 23 23 15 16 19 ︱\n";
cout<<"︱ 1 9 26 20 3 15 22 8 7 1 13 11 ︱\n";
cout<<"︱ 14 9 1 21 4 2 17 5 12 13 12 4 ︱\n";
cout<<"︱ 19 25 26 22 19 8 17 11 25 6 6 4 ︱\n";
cout<<"︱ 13 10 20 1 7 17 13 8 3 16 7 3 ︱\n";
cout<<"︱ 17 7 22 19 5 4 26 2 23 2 20 10 ︱\n";
cout<<"︱ 9 5 14 12 3 6 15 14 12 16 11 26 ︱\n";
cout<<"└———————————————————┘\n\n";
cout<<"请确保输入的数据符合样例的规范！\n\n";
}
if(mode==1) // 从键盘读入行、列和各个点的图案
{
cout<<"输入行数r（2≤r≤12）和列数c（2≤c≤20）\n";
cin>>r>>c;
if(r<=1||c<=1||r>MAX_HEIGHT||c>MAX_WIDTH)
{
cout<<"输入数据出错！\n";
return 0;
}
cout<<"请依次输入图案的数字矩阵（用1到30的整数表示图案，用0表示空，不能全为空）\n";
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
cin>>pattern[i][j];
if(pattern[i][j]!=0)patternednum++;
if(pattern[i][j]>PATTERN_NUM||pattern[i][j]<0)
{
cout<<"输入数据出错！\n";
return 0;
}
else patternnum[pattern[i][j]]++;
}
}
else if(mode==2) // 从指定的文件读入行、列和各个点的图案
{
cout<<"输入文件的路径和文件名\n";
char filename[300];
cin.get();
cin.getline(filename,300,'\n');
ifstream infile;
infile.open(filename);
if(!infile)
{
cout<<"文件不存在！出错！\n";
return 0;
}
infile>>r>>c;
if(r<=1||c<=1||r>MAX_HEIGHT||c>MAX_WIDTH)
{
cout<<"输入数据出错！\n";
return 0;
}
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
infile>>pattern[i][j];
if(pattern[i][j]!=0)patternednum++;
if(pattern[i][j]>PATTERN_NUM||pattern[i][j]<0)
{
cout<<"输入数据出错！\n";
system("PAUSE");
return 0;
}
else patternnum[pattern[i][j]]++;
}
infile.close();
}
else // 从键盘输入行、列数，自动生成图案
{
cout<<"输入行数r（2≤r≤12）和列数c（2≤c≤20）\n";
cin>>r>>c;
if(r<=1||c<=1||r>MAX_HEIGHT||c>MAX_WIDTH)
{
cout<<"输入数据出错！\n";
return 0;
}
cout<<"\n
