[北邮大作业]俄罗斯方块OJ版题解思路

题目很难，题目也很简单。

这边是用cpp写的，参考基于Pierre Dellacherie算法（一下简称PD）

这边图形就根据数组定义建系

棋盘长这样：

1.     思路：

1.0   由于board是10*20 这使得暴力遍历能够实现

1.1   要知道俄罗斯方块下落停止的时候 必须在一个支撑点上 所以我们是不是可以根据这10个col点来当支撑点

1.2   既然有了支撑点 那么我们接下来该思考什么？是rotation? NO,我就是一直徘徊在这里，是接触的点！看一下这个图

这里为什么我的‘O’没有装在左边？先看col=0的这个接触点 由于右边被填充了，所以我就只能放弃掉col=0，再看col=1这个点，同理 我也会放弃这个点，因为我的坐标偏移量是这样设计的：

{'O',{{{0,0},{1,0},{0,1},{1,1}}}},//0

由于我只考虑一个接触点 忽略了其他接触点 所以我的‘O’始重无法填充左边空间。

1.3  接下来我们需要考虑是接触点

比如‘I’

它是这样的

所以要遍历4个偏移量 这个for长度根据宽度设计

那我就不多说了 O一种 长度为2 共1*2

               ISZ两种 长度[1,4]

               TLJ三种 长度[1,3]

我用unordered_map:

unordered_map<char,vector<vector<vector<vector<int>>>>>

分别是：

第几种旋转

一共有多少个接触点

一个二维数组来记录偏移量

2.     想到找点方法后，我们需要设计一个结构体node

我是这样想的：

Int,x,y 做一个支持点坐标

Bool is_dead 进行筛选（碰撞，越界）

Vector<pair<int,int>>来记录方块坐标

Int angle,min_y 这里进行记录 方便后面输出

还有一个重要变量double sumScore 用来后面进行pk 选出最优位置

3.     有点，有结构体，才有记录，才能打pk，才能记录Pk元素参数求取

终于到了PD算法

这6个参数我也思考了很久，也算是写出来了（注意，这里是填充后的board，而不是消行后的board）

3.1高度：坐标填充后,我们从row=0开始向上遍历 知道sumRow=0 全是空的 我们就结束遍历 return height.

3.2贡献：如果有消行，那就看一下填充坐标有几个在该被消行上 假如消了2行，有三个点坐标在这个被消行上，那就return 2*3;

3.3行变(rowTran)：按行遍历，从board[?][0]开始向右遍历10个点 实心->空心为一次变化 空心->实心为一次变化 return sumChanges.

3.4列变（colTran）:按列遍历 同理跟3一样 return sumChanges.

这里可以参考一下这个图

colTran=14,rowTran=37.看看你想对了没。

3.5空洞（hole）:按列遍历，找到一个实心点，再找到一个实心点或者为边界，就算一个空洞。

猜一下有几个空洞？ 答案是9个

3.6#数（well）： 顾名思义，就是左右不通。按列遍历，找到空格，保证左右不通，然后判断是否增加#深（depth）,先看一下col==0这一列 共有3+1+4，则该列要返回(1+2+3)+(1)+ (1+2+3+4)=17,然后遍历所有列，最后返回sum。主要是出现#很难填充，所以惩罚力度比较大。（吐槽一下，这里用了3个不同的dfs来进行边界和中心的遍历，实在是没招了）

4. 最后用max_element(v.begin(),v.end(),mycompare)进行遍历，写一个仿函数来比较两个结构体return n1.sumScore<n2.sumScore,获取最有位置。后面进行填充，检查，更新得分，移除满行，进行简单的动态模拟就好了！

Cout << it->angle<<” ” <<it->min_y << “\n” << SCORE<< “\n”;

Haha!

具体完成代码，考虑到作业的原因就不发来了，欢迎交流~