消消乐实验回溯法（深大算法实验3）报告+代码
程序员文章站
2024-03-22 17:06:40
...
所有实验的资源
链接: https://pan.baidu.com/s/1lukZRM3Rsd1la35EyyJcvg
提取码: iv72
目录
写在前面
期末终于算法课快要完结了。
这学期算法课可谓是最难顶的课程了，又正好是线上上课，提问互动的机会相对较少，老师上课抛砖引玉，实验内容又比较难，我花了大部分的时间在找算法，实现算法，改算法bug上。
我也参考过很多往届师兄的报告，但是大多都比较抽象晦涩，而且没有代码只讲方法，比较难以理解具体实现的细节。
所以我打算记录一下自己的报告+代码，前人coding后人copying ，希望让大家少走弯路。。。
注意：不要直接copy代码，这是冲塔行为！查重系统鲨疯辣。
实验要求
消消乐问题，如果有连续三个同类方块，那么消去得1分，4个4分，5个10分，K为方块的种类，M,N为棋盘尺寸，X为可以移动的次数
- 给定K, M, N编写代码计算通过一步操作（X=1）可得的最大得分。
例如，K=4, M=8, N=4
测试数据
3 3 4 3
3 2 3 3
2 4 3 4
1 3 4 3
3 3 1 1
3 4 3 3
1 4 4 3
1 2 3 2
-
在1的基础上利用回溯算法，找出X交换步骤之后的最大得分。
-
对于数值较大的K、M、N、X，在允许近似最优解的情况下，对2中实现的算法进行优化剪枝。并与内容2中最终结果和执行速度进行比较。
-
如果能实现可视化输出计算结果（包括回溯过程），如图2，可加分。
实验要求：
- 对不同K，M, N, X的问题依次求解，演示你的求解结果，请提供你机器上能求解的问题最大规模。
- 在blackboard提交电子版实验报告。源代码和PPT作为实验报告附件上传。
- 在实验完成之后，将进行一次PPT介绍。
- 在实验报告中要求详细说明”实验内容1”和“实验内容2”的实现思想。
- 讨论”实验内容1”和“实验内容2”问题复杂度和K, M, N, X的关系。
求解问题的算法原理描述
对于棋盘中的每一个方块，我们都可以做四个操作：与 上 下 左 右 交换
对于每个操作，都可能产生方块的消除，进而产生新的棋盘状态，而这些新状态又可以继续操作，进而可以通过回溯法遍历每个状态来查看所有操作的可能的得分，找到最大的得分
剪枝优化：不一定要对所有的状态都进行递归，而是选取前topk大的状态进行递归，这很容易剪掉一些显然不可能是最大答案的分支，topk的选择可以是1，3，5，7，….
记忆化：在回溯法的基础上，将答案保存，如果遇到相同状态的棋盘，不必再次求解，直接取保存的答案，节省计算的时间开销
在代码中，通过交换两个方块并且尝试消除，得到消除之后的棋盘，再次尝试消除，这个过程通过递归直到无法消除（因为消除之后可能又有三联的情况出现）
在记忆化保存状态的时候，将棋盘转换为字符串，再计算棋盘的哈希，做哈希map映射来实现记忆化递归
算法实现的核心伪代码
回溯法
回溯法+剪枝，只保留前k大的状态
记忆化递归：
算法测试结果及效率分析
回溯法：得分测试
最大得分测试：样例：老师提供的样例 k=4 n=8 m=4 x=1,2,3,4,5,6,7,8,9
移动一次：
回溯法最大得分 4
移动两次：
回溯法最大得分：9
移动三次
回溯法最大得分：15
移动四次
回溯法最大得分：17
移动五次
回溯法最大得分：20
移动6次
回溯法最大得分：21
移动7次：
回溯法最大得分：22
移动8次：
回溯法最大得分：20
移动9次
回溯法最大得分：15
移动10次
无 法 做 到 移 动 十 次
回溯法：最大规模
因为数据是随机生成的关系，时间并不好测量，具有很大的随机性，如下例子
K=8 m=8 n=8 x=7 用时79.054 s
K=8 m=9 n=9 x=7 用时12.284 s
但是这个规模K=8 m=9 n=9 x=5的随机样例，经过大量测试，能在15s左右解完
可以近似认为这就是求解问题的最大规模了
回溯法：时间复杂度
每一个棋盘都有mn个方块，每个方块有4种可能的移动方式，一共4mn种新状态，而消去方块的复杂度是O(mn)，对每种状态都要消去方块，操作的次数是x意味着递归的深度是x，时间复杂度O((m*n*m*n)x) = O((m*n)2x)
时间测试
测试规模：k=6 m=8 n=8 x=1,2,3,4,5，横坐标操作次数，纵坐标时间(s)
因为回溯法用时太长，导致图表结果不够直观，我们去掉回溯法的用时（如下图表）
总结：可以看到回溯法用时最长，记忆化有效缩短了时间，而剪枝过后时间大大短于回溯法，其中只保留最大的前1个分支，即topk=1的剪枝回溯法（其实退化为贪心法了）耗时最短，只保留最大的前7个分支，即topk=7的剪枝回溯法，用时最长，且所有剪枝回溯法的用时都与topk成正相关，topk越大，保留分支越多，用时越长，这也符合我们的认知
回溯法：不同参数规模的影响
可以看到随着k（方块种类）的增加，时间消耗逐渐减小，因为大的k提供了更少的消除可能性
可以看到随着m（行数）的增加，时间开销逐渐增大，因为更大的m，使得每一个棋盘的情况变多，使得搜索的分支数增加
可以看到随着n（列数）的增加，时间开销逐渐增大，因为更大的n，使得每一个棋盘的情况变多，使得搜索的分支数增加，但是与行数m对比，n对时间开销的改变没有m那么大，因为m更多的决定了消去的可能（消去方块后，沿着行方向掉落）
回溯法与剪枝回溯法：得分测试
测试规模：k=6 m=8 n=8 x=1,2,3,4,5，横坐标操作次数，纵坐标得分
总结：可以看到，回溯法和记忆回溯法的得分总是最大的，因为回溯法是全局最优解
而剪枝回溯法，随着保留的分支数目的增加，即随着topk的增加，得分逐渐逼近回溯法的得分（上界），这表明保留的分支越多，越容易逼近全局最优解，这也符合我们的认知
时间与得分 分析：
可以看到保留7或5个分支的剪枝回溯法最能够逼近最优解，而且耗时相当少，而且在可以接受的程度
而保留3个分支的剪枝回溯法在得分上稍显劣势，但是运行速度比5或7的剪枝快很多
而保留1个分支（即贪心法）是最快的，但是得出的得分却很低，因为一个具有丰富技巧的消消乐选手往往需要通过舍弃局部最优，来为后续的消去拼凑更优的解，这和贪心的“无后效性”矛盾，自然不能用贪心法得出最优解
带记忆化的回溯法可以有效缩短时间，但是在面对大规模问题，仍然具有相当的时间复杂度
图形演示
由于word无法展示动图，所以老师请关注我的实验答辩及ppt，或者是移步到我的GitHub上查看详细的演示
https://github.com/AKGWSB/grapic-demo-of-XiaoXiaoLe-algorithm
对求解这个问题的经验总结
记忆化的回溯法能够有效减少时间开销，而且节省的时间开销随着规模的扩大而增加，但是在小规模问题时，因为查询和保存操作需要一定的时间，所以会略慢于回溯法，而查询和插入的过程可以通过更好的哈希函数来解决
消去方块后可能形成新的可以消去的方块，这点在计算得分的时候及其容易出错，消去方块一定要保证消到无可在消，这个过程可以用递归进行
因为回溯法是递归的，一旦有错误满盘皆错，所以在递归之前，应该改好一次回溯法的bug，否则调试起来非常困难
回溯法一定要通过小规模样例，打印回溯过程，以及结果，以确保正确性
因为for循环ij从小到大，坐标系是 ↓→ 而不是↑→，在debug的时候要注意
代码
消消乐
#include <bits/stdc++.h>
using namespace std;
int k, m, n, ans=0;
vector<vector<int>> path, p;
int iabs(int x){return (x>=0)?(x):(-x);}
/*
function : print 打印矩阵
param mat : 要打印的矩阵的引用
return : ----
*/
void print(vector<vector<int>>& mat)
{
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++) cout<<mat[i][j]<<" ";
cout<<endl;
}
}
/*
function : 交换两个数字
param n1 : 第一个数字的引用
param n2 : 第二个数字的引用
return : ----
*/
void bswap(int& n1, int& n2)
{
n1 ^= n2;
n2 ^= n1;
n1 ^= n2;
}
/*
function : erase 消去方块并且使剩余方块下落
param mat : 方块数组的引用
return : 消去所有可能的方块后最大得分
explain : 遍历棋盘以计算是否出现3连号或者以上 复杂度为O(m*n)
: 因为消去而产生的新的相邻3连也会被计算(返回时尾递归)
*/
int erase(vector<vector<int>>& mat)
{
int cnt3=0, cnt4=0, cnt5=0;
// 计算3，4，5的连续块个数
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
if(i+2<m && mat[i][j]!=0) // 长度为3，纵块
{
if(iabs(mat[i][j])==iabs(mat[i+1][j])&&
iabs(mat[i+1][j])==iabs(mat[i+2][j]))
mat[i][j]=mat[i+1][j]=mat[i+2][j]=-iabs(mat[i][j]), cnt3++;
}
if(j+2<n && mat[i][j]!=0) // 长度为3，横块
{
if(iabs(mat[i][j])==iabs(mat[i][j+1])&&
iabs(mat[i][j+1])==iabs(mat[i][j+2]))
mat[i][j]=mat[i][j+1]=mat[i][j+2]=-iabs(mat[i][j]), cnt3++;
}
if(i+3<m && mat[i][j]!=0) // 长度为4，纵块
{
if(iabs(mat[i][j])==iabs(mat[i+1][j])&&
iabs(mat[i+1][j])==iabs(mat[i+2][j])&&
iabs(mat[i+2][j])==iabs(mat[i+3][j]))
mat[i][j]=mat[i+1][j]=mat[i+2][j]=mat[i+3][j]=-iabs(mat[i][j]), cnt4++;
}
if(j+3<n && mat[i][j]!=0) // 长度为4，横块
{
if(iabs(mat[i][j])==iabs(mat[i][j+1])&&
iabs(mat[i][j+1])==iabs(mat[i][j+2])&&
iabs(mat[i][j+2])==iabs(mat[i][j+3]))
mat[i][j]=mat[i][j+1]=mat[i][j+2]=mat[i][j+3]=-iabs(mat[i][j]), cnt4++;
}
if(i+4<m && mat[i][j]!=0) // 长度为5，纵块
{
if(iabs(mat[i][j])==iabs(mat[i+1][j])&&
iabs(mat[i+1][j])==iabs(mat[i+2][j])&&
iabs(mat[i+2][j])==iabs(mat[i+3][j])&&
iabs(mat[i+3][j])==iabs(mat[i+4][j]))
mat[i][j]=mat[i+1][j]=mat[i+2][j]=mat[i+3][j]=mat[i+4][j]=-iabs(mat[i][j]), cnt5++;
}
if(j+4<n && mat[i][j]!=0) // 长度为5，横块
{
if(iabs(mat[i][j])==iabs(mat[i][j+1])&&
iabs(mat[i][j+1])==iabs(mat[i][j+2])&&
iabs(mat[i][j+2])==iabs(mat[i][j+3])&&
iabs(mat[i][j+3])==iabs(mat[i][j+4]))
mat[i][j]=mat[i][j+1]=mat[i][j+2]=mat[i][j+3]=mat[i][j+4]=-iabs(mat[i][j]), cnt5++;
}
}
}
// 方块下落
for(int j=0; j<n; j++)
{
int st=m-1, ed=0, dst=0, delta=0;
while(st>=0 && mat[st][j]>0) st--;
for(ed=st; ed>=0&&mat[ed][j]<=0; ed--){}
delta = st-ed;
for(int i=ed; i>=0; i--)
mat[i+delta][j]=mat[i][j], mat[i][j]=0;
}
for(int i=0; i<m; i++)
for(int j=0; j<n; j++) mat[i][j]=max(mat[i][j], 0);
cnt4-=2*cnt5, cnt3-=(3*cnt5+2*cnt4); // 消去重复的计数
if(cnt3 + cnt4*4 + cnt5*10 == 0) return 0; // 是否需要消去新的连号
return cnt3 + cnt4*4 + cnt5*10 + erase(mat);
}
/*
function : dfs 深度优先搜索，搜最大得分的消去方式
param mat : 方块数组的引用
param step : 执行交换的次数
param sum : 当前递归树节点得分值
return : ----
explain : 最优答案（全局变量）会在递归达到最深时被更新
*/
void dfs(vector<vector<int>>& mat, int step, int sum)
{
if(step==0)
{
if(sum > ans)
ans=sum, path=p;
return;
}
vector<vector<int>> a;
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
if(i+1<m && mat[i][j] && mat[i+1][j])
{
a=mat, bswap(a[i][j], a[i+1][j]);
int res = erase(a);
if(res>0)
{
p.push_back(vector<int>{i,j,i+1,j});
dfs(a, step-1, sum+res);
p.pop_back();
}
}
if(j+1<n && mat[i][j] && mat[i][j+1])
{
a=mat, bswap(a[i][j], a[i][j+1]);
int res = erase(a);
if(res>0)
{
p.push_back(vector<int>{i,j,i,j+1});
dfs(a, step-1, sum+res);
p.pop_back();
}
}
}
}
}
/*
function cmp : 比较函数，存储状态时对状态按照得分降序排序时使用
param v1 : 第1个状态的引用
param v2 : 第2个状态的引用
return : 比较结果
explain : 状态保存为一维数组[得分,x1,y1,x2,y2] xy为交换的方块的坐标
*/
bool cmp(const vector<int>& v1, const vector<int>& v2)
{
return v1[0]>v2[0];
}
/*
function : 贪心法+dfs：每次选择得分前 k 大的分支
param mat : 方块数组的引用
param step : 执行交换的次数
param tpk : 选择前 tpk 大的状态进行递归
return : ----
explain : 不能保证得到最优解
*/
void dfs_topk(vector<vector<int>>& mat, int step, int sum, int tpk)
{
if(step==0)
{
if(sum > ans)
ans=sum, path=p;
return;
}
vector<vector<int>> a, seq;
int maxv=0,x1=0,y1=0,x2=0,y2=0,res;
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
if(i+1<m && mat[i][j] && mat[i+1][j])
{
a=mat, bswap(a[i][j], a[i+1][j]);
res = erase(a);
if(res > maxv) seq.push_back(vector<int>{res,i,j,i+1,j});
}
if(j+1<n && mat[i][j] && mat[i][j+1])
{
a=mat, bswap(a[i][j], a[i][j+1]);
res = erase(a);
if(res > maxv) seq.push_back(vector<int>{res,i,j,i,j+1});
}
}
}
sort(seq.begin(), seq.end(), cmp);
for(int i=0; i<min((int)seq.size(),tpk); i++)
{
a=mat, bswap(a[seq[i][1]][seq[i][2]], a[seq[i][3]][seq[i][4]]);
res = erase(a);
p.push_back(vector<int>(seq[i].begin()+1, seq[i].end()));
dfs_topk(a, step-1, sum+res, tpk);
p.pop_back();
}
}
/*
function : mat2str 矩阵转为字符串，为下面hashmap查表做key用
param v : 棋盘矩阵
param step : 当前走的步数
return : 转换后的字符串，因为STL有提供string的hash函数，方便做key查表
*/
string mat2str(vector<vector<int>>& v, int step)
{
string str = "";
for(int i=0; i<v.size(); i++)
for(int j=0; j<v[0].size(); j++) str += (char)(v[i][j]+'0');
str += (char)(step+'0');
return str;
}
/* hashmap 哈希表保存棋盘状态与得分，key=棋盘 value=得分 */
unordered_map<string, int> hashmap;
/*
function : dfs + mem 记忆化的深度优先搜索，也是动态规划的一种实现
param mat : 方块数组的引用
param step : 执行交换的次数
return : 当前棋盘能够获得的最大价值
explain : 采用记忆化的策略，计算答案之前先查看这个棋盘是否之前被计算过
: 得到的是全局最优解
*/
int dfs_mem(vector<vector<int>>& mat, int step)
{
if(step==0) return 0;
// 递归前先查表，有则直接返回
vector<vector<int>> a;
string key = mat2str(mat, step);
if(hashmap[key] != 0) return hashmap[key];
// 穷举状态开始递归
int maxv=0, val=0;
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
if(i+1<m && mat[i][j] && mat[i+1][j])
{
a=mat, bswap(a[i][j], a[i+1][j]);
int res = erase(a);
if(res>0)
{
p.push_back(vector<int>{i,j,i+1,j});
val = dfs_mem(a, step-1);
maxv = max(maxv, val+res);
p.pop_back();
}
}
if(j+1<n && mat[i][j] && mat[i][j+1])
{
a=mat, bswap(a[i][j], a[i][j+1]);
int res = erase(a);
if(res>0)
{
p.push_back(vector<int>{i,j,i,j+1});
val = dfs_mem(a, step-1);
maxv = max(maxv, val+res);
p.pop_back();
}
}
}
}
// 保存这一次的结果
hashmap[key] = maxv;
return maxv;
}
/*
function : printPath 打印一次dfs之后获得的路径以及答案
param name : 方法名称
param src : 路径的目标棋盘矩阵 引用
return : ----
*/
void printPath(string name, vector<vector<int>> src)
{
cout<<endl<<" >>> "<<name<<"过程如下: <<<"<<endl<<endl;
print(src);
for(int k=0; k<path.size(); k++)
{
cout<<"对上面 ↑棋盘进行交换 ";
cout<<"("<<path[k][0]<<","<<path[k][1]<<") <--> ";
cout<<"("<<path[k][2]<<","<<path[k][3]<<") "<<"得到下面的棋盘 ↓:"<<endl;
cout<<"棋盘状态:"<<endl;
bswap(src[path[k][0]][path[k][1]], src[path[k][2]][path[k][3]]);
erase(src);
print(src);
}
cout<<name<<"最大得分是: "<<ans<<endl;
}
int main()
{
#define k_types 6
#define row 7
#define col 7
#define x_step 1
#define select_top_k 3
#define sample 20
k=k_types, m=row, n=col;
clock_t start, end;
/*
// 去掉这部分的注释可以实现：实验要求1 手动输入数据，计算不同x，不同算法得分
vector<vector<int>> mat(m), m1, m2;
for(int i=0; i<m; i++) mat[i].resize(n);
for(int i=0; i<m; i++)
for(int j=0; j<n; j++) cin>>mat[i][j];
// 回溯法
ans=0, m1=mat;
start = clock();
dfs(m1, x_step, 0);
end = clock();
printPath("回溯法", m1);
cout<<"回溯法用时: "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<endl;
// 回溯+贪心,选择前 select_top_k 大的分支进行dfs
ans=0, m2=mat;
start = clock();
dfs_topk(m2, x_step, 0, select_top_k);
end = clock();
printPath("回溯+贪心法", m2);
cout<<"回溯+贪心法用时: "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<endl;
*/
/*
// 去掉这部分的注释可以实现：实验要求2 随机生成数据，测试极限规模
default_random_engine rd(time(NULL));
uniform_int_distribution<int> dist(1, k_types);
vector<vector<int>> mat(m), m1, m2;
for(int i=0; i<m; i++) mat[i].resize(n);
while(1)
{
for(int i=0; i<m; i++)
for(int j=0; j<n; j++) mat[i][j]=dist(rd);
if(erase(mat)==0) break;
}
cout<<"数据生成完毕, 执行步数为 "<<x_step<<endl;
ans=0, m1=mat;
start = clock();
dfs(m1, x_step, 0);
end = clock();
printPath("回溯法", m1);
cout<<"回溯法用时: "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<endl;
*/
// 实验要求3 随机生成数据，测试时间
double t1=0,t2=0,t3=0,t4=0,t5=0,t6=0,s1=0,s2=0,s3=0,s4=0,s5=0,s6=0;
default_random_engine rd(time(NULL));
uniform_int_distribution<int> dist(1, k_types);
int tt = sample;
while(tt--)
{
vector<vector<int>> mat(m), m1;
for(int i=0; i<m; i++) mat[i].resize(n);
while(1)
{
for(int i=0; i<m; i++)
for(int j=0; j<n; j++) mat[i][j]=dist(rd);
if(erase(mat)==0) break;
}
cout<<"数据生成完毕 "<<sample-tt<<endl;
// 回溯法
ans=0, m1=mat;
start = clock();
dfs(m1, x_step, 0);
end = clock();
t1 += (double)(end-start)/CLOCKS_PER_SEC;
s1 += ans;
// 每次递归最大的前 1 个分支
ans=0, m1=mat;
start = clock();
//dfs_topk(m1, x_step, 0, 1);
end = clock();
t2 += (double)(end-start)/CLOCKS_PER_SEC;
s2 += ans;
// 每次递归最大的前 3 个分支
ans=0, m1=mat;
start = clock();
//dfs_topk(m1, x_step, 0, 3);
end = clock();
t3 += (double)(end-start)/CLOCKS_PER_SEC;
s3 += ans;
// 每次递归最大的前 5 个分支
ans=0, m1=mat;
start = clock();
//dfs_topk(m1, x_step, 0, 5);
end = clock();
t4 += (double)(end-start)/CLOCKS_PER_SEC;
s4 += ans;
// 每次递归最大的前 7 个分支
ans=0, m1=mat;
start = clock();
//dfs_topk(m1, x_step, 0, 7);
end = clock();
t5 += (double)(end-start)/CLOCKS_PER_SEC;
s5 += ans;
// 记忆化
ans=0, m1=mat;
hashmap.clear(); // 清除记忆
start = clock();
//ans = dfs_mem(m1, x_step);
end = clock();
t6 += (double)(end-start)/CLOCKS_PER_SEC;
s6 += ans;
}
cout<<"步数为 "<<x_step<<endl;
cout<<"回溯: 平均用时 "<<t1/sample<<" s, 平均得分 "<<s1/sample<<endl;
cout<<"topk=1 平均用时 "<<t2/sample<<" s, 平均得分 "<<s2/sample<<endl;
cout<<"topk=3 平均用时 "<<t3/sample<<" s, 平均得分 "<<s3/sample<<endl;
cout<<"topk=5 平均用时 "<<t4/sample<<" s, 平均得分 "<<s4/sample<<endl;
cout<<"topk=7 平均用时 "<<t5/sample<<" s, 平均得分 "<<s5/sample<<endl;
cout<<"记忆化 平均用时 "<<t6/sample<<" s, 平均得分 "<<s6/sample<<endl;
cout<<t1/sample<<endl;
cout<<t2/sample<<endl;
cout<<t3/sample<<endl;
cout<<t4/sample<<endl;
cout<<t5/sample<<endl;
cout<<t6/sample<<endl<<endl;
cout<<s1/sample<<endl;
cout<<s2/sample<<endl;
cout<<s3/sample<<endl;
cout<<s4/sample<<endl;
cout<<s5/sample<<endl;
cout<<s6/sample<<endl<<endl;
return 0;
}
/*
样例1
3 3 4 3
3 2 3 3
2 4 3 4
1 3 4 3
3 3 1 1
3 4 3 3
1 4 4 3
1 2 3 2
自定义样例
3 3 4 3 1 3 4 3
3 2 3 3 1 2 3 2
2 4 3 4 3 3 1 1
1 3 4 3 2 4 3 4
3 3 1 1 3 3 1 1
3 4 3 3 2 4 3 4
1 4 4 3 1 2 3 2
1 2 3 2 4 3 2 1
// 测试消除结果 样例 debug用
3 4 3 3
3 2 4 3
2 3 3 4
1 4 4 3
3 3 1 1
4 4 1 3
1 3 1 3
1 1 1 1
0 0 0 0
0 3 4 3
0 2 3 3
3 4 3 4
3 3 4 3
2 4 3 3
1 4 4 3
1 2 3 2
0 3 4 3
0 2 3 3
0 4 3 4
3 3 4 3
3 1 1 1
2 4 3 3
1 4 4 3
1 2 3 2
*/
图形演示
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import copy
'''
Author : RuoLongLi 2018171028 @SZU @CSSE
time : 2020/4/28
function : A graphic demo of 'xiao xiao le' game's backtracking(dfs) algorithm
input : a m*n mat, mat[i][j] represents the color of blocks (i, j)
output : a graphic demo (include backtracking process)
作 者 : 李若龙 2018171028 深大计软
时 间 : 2020 年 4 月 28 号
功 能 : 消消乐实验回溯法图形演示
输 入 : m*n的矩阵，mat[i][j] 表示 (i,j) 位置的颜色
输 出 : 图形颜色结果（包含回溯过程）
'''
'''
sample input:
样例输入:
3 3 4 3
3 2 3 3
2 4 3 4
1 3 4 3
3 3 1 1
3 4 3 3
1 4 4 3
1 2 3 2
'''
colors = ['white', 'red', 'blue', 'yellow', 'black']
k,m,n,x = 4,8,4,3
artists = []
'''
function : getCir 得到所有圆的artist对象
param mat : 棋盘数组
return : 所有圆的artist对象(list[])
'''
def getCir(mat):
fr = []
for i in range(m):
for j in range(n):
fr += plt.plot(j*10+40,80-i*10, "o", color=colors[mat[i][j]], markersize=19)
return fr
# 绝对值
def iabs(x):
if x<0:
return -x
return x
# 打印矩阵
def printm(mat):
for i in range(m):
for j in range(n):
print(mat[i][j],' ', end='')
print()
print()
# 根据坐标在frame帧上绘制矩形
def getRectangle(frame, x1, y1, x2, y2, c):
frame += plt.plot([x1, x2], [y1, y1], color=c)
frame += plt.plot([x1, x2], [y2, y2], color=c)
frame += plt.plot([x1, x1], [y1, y2], color=c)
frame += plt.plot([x2, x2], [y1, y2], color=c)
return frame
'''
function : erase 消去方块并且使方块下落
param mat : 棋盘数组的引用
return : 消去后增加的得分
'''
def erase(mat):
cnt3,cnt4,cnt5 = 0,0,0
# 计算3，4，5的连续块个数
for i in range(m):
for j in range(n):
if i+2<m and mat[i][j]!=0 :
if (iabs(mat[i][j])==iabs(mat[i+1][j]) and
iabs(mat[i+1][j])==iabs(mat[i+2][j])):
mat[i][j]=-iabs(mat[i][j])
mat[i+1][j]=-iabs(mat[i][j])
mat[i+2][j]=-iabs(mat[i][j])
cnt3 += 1
if j+2<n and mat[i][j]!=0 :
if (iabs(mat[i][j])==iabs(mat[i][j+1]) and
iabs(mat[i][j+1])==iabs(mat[i][j+2])) :
mat[i][j]=-iabs(mat[i][j])
mat[i][j+1]=-iabs(mat[i][j])
mat[i][j+2]=-iabs(mat[i][j])
cnt3 += 1
if i+3<m and mat[i][j]!=0 :
if (iabs(mat[i][j])==iabs(mat[i+1][j]) and
iabs(mat[i+1][j])==iabs(mat[i+2][j]) and
iabs(mat[i+2][j])==iabs(mat[i+3][j])):
mat[i][j]=-iabs(mat[i][j])
mat[i+1][j]=-iabs(mat[i][j])
mat[i+2][j]=-iabs(mat[i][j])
mat[i+3][j]=-iabs(mat[i][j])
cnt4 += 1
if j+3<n and mat[i][j]!=0:
if (iabs(mat[i][j])==iabs(mat[i][j+1]) and
iabs(mat[i][j+1])==iabs(mat[i][j+2]) and
iabs(mat[i][j+2])==iabs(mat[i][j+3])) :
mat[i][j]=-iabs(mat[i][j])
mat[i][j+1]=-iabs(mat[i][j])
mat[i][j+2]=-iabs(mat[i][j])
mat[i][j+3]=-iabs(mat[i][j])
cnt4 += 1
if i+4<m and mat[i][j]!=0:
if (iabs(mat[i][j])==iabs(mat[i+1][j]) and
iabs(mat[i+1][j])==iabs(mat[i+2][j]) and
iabs(mat[i+2][j])==iabs(mat[i+3][j]) and
iabs(mat[i+3][j])==iabs(mat[i+4][j])):
mat[i][j]=-iabs(mat[i][j])
mat[i+1][j]=-iabs(mat[i][j])
mat[i+2][j]=-iabs(mat[i][j])
mat[i+3][j]=-iabs(mat[i][j])
mat[i+4][j]=-iabs(mat[i][j])
cnt5 += 1
if j+4<n and mat[i][j] != 0:
if (iabs(mat[i][j])==iabs(mat[i][j+1]) and
iabs(mat[i][j+1])==iabs(mat[i][j+2]) and
iabs(mat[i][j+2])==iabs(mat[i][j+3]) and
iabs(mat[i][j+3])==iabs(mat[i][j+4])):
mat[i][j]=-iabs(mat[i][j])
mat[i][j+1]=-iabs(mat[i][j])
mat[i][j+2]=-iabs(mat[i][j])
mat[i][j+3]=-iabs(mat[i][j])
mat[i][j+4]=-iabs(mat[i][j])
cnt5 += 1
# 方块下落
for j in range(n):
st = m-1
while st>=0 and mat[st][j]>0 :
st -= 1
ed = st
while ed>=0 and mat[ed][j]<=0 :
ed -= 1
delta = st-ed
for i in range(ed,-1,-1):
mat[i+delta][j] = mat[i][j]
mat[i][j] = 0
for i in range(m):
for j in range(n):
if mat[i][j]<0 :
mat[i][j] = 0
# 消去重复的计数
cnt4 -= 2*cnt5
cnt3 -= (3*cnt5 + 2*cnt4)
if cnt3+cnt4*4+cnt5*10 == 0 :
return 0
return cnt3 + cnt4*4 + cnt5*10 + erase(mat)
'''
function : dfs_tpk
param mat : 消消乐棋盘矩阵
param step : 当前递归树的深度
param sum : 当前得分和
param tpk : 选取前 tpk 大的分支进行递归
return : ----
'''
def dfs_tpk(mat, step, sum, tpk):
if step==0 :
return
seq = []
# 消去检测，获得所有分支
for i in range(m):
for j in range(n):
if i+1<m and mat[i][j]>0 and mat[i+1][j]>0 :
a = copy.deepcopy(mat)
a[i][j],a[i+1][j] = a[i+1][j],a[i][j]
res = erase(a)
if res>0 :
seq.append([res,i,j,i+1,j])
if j+1<n and mat[i][j]>0 and mat[i][j+1]>0 :
a = copy.deepcopy(mat)
a[i][j], a[i][j+1] = a[i][j+1], a[i][j]
res = erase(a)
if res>0 :
seq.append([res,i,j,i,j+1])
# 按照得分排序
for i in range(seq.__len__()):
for j in range(seq.__len__()-1):
if seq[j][0] < seq[j+1][0]:
seq[j],seq[j+1] = seq[j+1],seq[j]
# 递归tpk大的分支
for i in range(min(seq.__len__(), tpk)):
a = copy.deepcopy(mat)
artists.append(getCir(a))
# 打印矩形框同时打印方块们
x1,y1,x2,y2 = seq[i][1],seq[i][2],seq[i][3],seq[i][4]
x1,x2 = min(x1,x2), max(x1,x2)
y1,y2 = min(y1,y2), max(y1,y2)
y1-=0.5
y2+=0.5
x1-=0.5
x2+=0.5
artists.append(getRectangle(getCir(a),y1*10+40,80-x1*10,y2*10+40,80-x2*10, 'red'))
a[seq[i][1]][seq[i][2]], a[seq[i][3]][seq[i][4]] = a[seq[i][3]][seq[i][4]], a[seq[i][1]][seq[i][2]]
artists.append(getRectangle(getCir(a),y1*10+40,80-x1*10,y2*10+40,80-x2*10, 'blue'))
# 消除方块，递归
res = erase(a)
dfs_tpk(a, step-1, sum+res, tpk)
# 回溯打印
artists.append(getCir(a))
if __name__ == '__main__':
mat = []
for i in range(m):
mat.append(list(map(int,input().split(" "))))
'''
for i in range(m):
for j in range(n):
print(mat[i][j], end='')
print()
'''
fig = plt.figure()
plt.xlim(-10, 140)
plt.ylim(-10, 100)
mngr = plt.get_current_fig_manager() # 获取当前figure manager
mngr.window.wm_geometry("+380+50") # 调整窗口在屏幕上弹出的位置
dfs_tpk(mat, 3, 0, 3)
ain = animation.ArtistAnimation(fig=fig, artists=artists, interval=1000)
plt.show()
ain.save('demo.gif', fps=2)