题解 P1312 【Mayan游戏】
BT狸——Frozen
·
·
题解
题解
第一次过了一道Day1最后一题，心中还是有点激动。
这道题目空间小，时间多，由此可见是一道码量极大的题。
既然如此，我们就将它拆分一下。
- 输入
本题的输入是第一个坑，我开始把(0,0)的位置看错了，于是后面直接崩溃。题中输入时横着输入的，那么我们要处理一下
void in()
{
int a;
for (int i=0;i<5;i++) //先是横坐标
for (int j=0;;j++) //后是纵坐标（坑）
{
scanf("%d",&a);
if(a) mp[i][j]=a;
else break;
}
}
题目中讲到，遇到0就换一列。但是\color{red}\text{注意:}如果1列的7行都有数字，输入时依然会有0，故我们不能自动换列（60分的惨痛经历）
- 掉落
掉落部分相对比较简单，我们只需要把所有方块自下而上得遍历，检查它们下面空方块就行了。
void down()
{
int m;
for (int i=0;i<5;i++)//自下而上
{
for (int j=1;j<7;j++)
{
if(mp[i][j])//这个方块有颜色
{
m=0;
while(j-m-1>=0 && !mp[i][j-m-1]) m++;//寻找最下面的空方块
if(m) mp[i][j-m]=mp[i][j],mp[i][j]=0;//下移
}
}
}
}
这个步骤没有什么大坑，就是下掉时防止越界。
- 清除
清除部分要特别注意题目中的情况。
由图5可知，我们不能遇到三个连块就直接消除，可能会无法完全消除。
那么，我们需要另一个结构体
struct mem{
int x,y;
}me[100];
在检测时，我们记录需要清除的方块，最后再一起清除。
bool clear()
{
int t=0;//计数器
for (int i=0;i<5;i++)
for (int j=0;j<7;j++)
{
if(mp[i][j])
{
if(i-1>=0 && i+1<=4 && mp[i-1][j]==mp[i][j] && mp[i+1][j]==mp[i][j])//横向
{
me[++t].x=i-1,me[t].y=j;
me[++t].x=i,me[t].y=j;
me[++t].x=i+1,me[t].y=j;//储存
}
if(j-1>=0 && j+1<=6 && mp[i][j-1]==mp[i][j] && mp[i][j+1]==mp[i][j])//纵向
{
me[++t].x=i,me[t].y=j-1;
me[++t].x=i,me[t].y=j;
me[++t].x=i,me[t].y=j+1;
}
}
}
if(t)//有需要清除的
for (int i=1;i<=t;i++)
mp[me[i].x][me[i].y]=0;//清除
else return 0;//未清除
return 1;//清除了
}
注意，清除过后可能有掉落的，所以要返回一个值，表示要掉落一次。
- 移动
移动是很简单的，类似于交换a,b。最后进行掉落和清除。
void mo(int x,int y,int d)
{
int t=mp[x][y];
mp[x][y]=mp[x+d][y];
mp[x+d][y]=t;//交换a,b
down();//掉落
while(clear()) down();//若有清除，则掉落
}
5. 备份与恢复
这一点就直接使用三维数组。
```cpp
void copy(int t)
{
for (int i=0;i<5;i++)
for(int j=0;j<7;j++)
memory[t][i][j]=mp[i][j];
}
void back(int t)
{
for (int i=0;i<5;i++)
for(int j=0;j<7;j++)
mp[i][j]=memory[t][i][j];
}
```
6. 检查
循环遍历，遇到有未清除的就返回。
```cpp
bool check()
{
for (int i=0;i<5;i++)
if(mp[i][0])
return 0;
return 1;
}
```
7. dfs
剪枝的方法与其它题解差不多。
>1. 由于我们是按字典序输出，所以从（0,0）开始向上向右遍历。
>2. 每个方块向右边走时右边一定要没有方块，否则会与前面的方块路径重叠。
```cpp
void dfs(int step)//第几步
{
if(check() && step<=n+1)//有符合条件的
{
for (int i=1;i<=step-1;i++)
{
printf("%d %d %d\n",s[i].x,s[i].y,s[i].move);
}
exit(0);//直接退出程序
}
if (step==n+1)//超出最大步数
return ;
copy(step);//备份
for (int i=0;i<5;i++)
for (int j=0;j<7;j++)
{
if(mp[i][j])// 方块存在
{
if(i-1>=0 && mp[i-1][j]==0)//向左
{
s[step].x=i,s[step].y=j,s[step].move=-1;
mo(i,j,-1);
dfs(step+1);
back(step);
s[step].x=0,s[step].y=0,s[step].move=0;
}
if (i+1<5 && mp[i+1][j]!=mp[i][j])//向右
{
s[step].x=i,s[step].y=j,s[step].move=1;
mo(i,j,1);
dfs(step+1);
back(step);
s[step].x=0,s[step].y=0,s[step].move=0;
}
}
}
}
```
那么，主体部分就完成了。
------------
### _关于调试_
对于一道这样的题，一次过是比较困难的，但是步骤这么多，一步一步调试是极其困难的（样例已经够恐怖了）那么，我们就可以写一个输出函数，利用文件输出，一步步输出，再检查。
```cpp
int out()
{
for (int j=7;j>=0;j--)
{
for (int i=0;i<5;i++)
{
if(mp[i][j]) printf("%d ",mp[i][j]);
else printf(" ");
}
printf("\n");
}
}
```
当然，洛谷上交时记得去掉。
------------
### _总结_
总的来说，只要将这题分割成一个个小部分，就可以系统地解决问题。
当然，码量高的后果就是调试难，建议大家一个函数一个函数排除问题，将包围圈逐渐缩小，就可以解决问题了。
------------
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int mp[10][10];
struct mem{
int x,y;
}me[100];
int memory[10][10][10];
int n;
struct st{
int x,y,move;
}s[10];
bool clear()
{
int t=0;//计数器
for (int i=0;i<5;i++)
for (int j=0;j<7;j++)
{
if(mp[i][j])
{
if(i-1>=0 && i+1<=4 && mp[i-1][j]==mp[i][j] && mp[i+1][j]==mp[i][j])//横向
{
me[++t].x=i-1,me[t].y=j;
me[++t].x=i,me[t].y=j;
me[++t].x=i+1,me[t].y=j;//储存
}
if(j-1>=0 && j+1<=6 && mp[i][j-1]==mp[i][j] && mp[i][j+1]==mp[i][j])//纵向
{
me[++t].x=i,me[t].y=j-1;
me[++t].x=i,me[t].y=j;
me[++t].x=i,me[t].y=j+1;
}
}
}
if(t)//有需要清除的
for (int i=1;i<=t;i++)
mp[me[i].x][me[i].y]=0;//清除
else return 0;//未清除
return 1;//清除了
}
void down()
{
int m;
for (int i=0;i<5;i++)//自下而上
{
for (int j=1;j<7;j++)
{
if(mp[i][j])//这个方块有颜色
{
m=0;
while(j-m-1>=0 && !mp[i][j-m-1]) m++;//寻找最下面的空方块
if(m) mp[i][j-m]=mp[i][j],mp[i][j]=0;//下移
}
}
}
}
void mo(int x,int y,int d)
{
int t=mp[x][y];
mp[x][y]=mp[x+d][y];
mp[x+d][y]=t;//交换a,b
down();//掉落
while(clear()) down();//若有清除，则掉落
}
bool check()
{
for (int i=0;i<5;i++)
if(mp[i][0])
return 0;
return 1;
}
void copy(int t)
{
for (int i=0;i<5;i++)
for(int j=0;j<7;j++)
memory[t][i][j]=mp[i][j];
}
void back(int t)
{
for (int i=0;i<5;i++)
for(int j=0;j<7;j++)
mp[i][j]=memory[t][i][j];
}
void dfs(int step)//第几步
{
if(check() && step<=n+1)//有符合条件的
{
for (int i=1;i<=step-1;i++)
{
printf("%d %d %d\n",s[i].x,s[i].y,s[i].move);
}
exit(0);//直接退出程序
}
if (step==n+1)//超出最大步数
return ;
copy(step);//备份
for (int i=0;i<5;i++)
for (int j=0;j<7;j++)
{
if(mp[i][j])// 方块存在
{
if(i-1>=0 && mp[i-1][j]==0)//向左
{
s[step].x=i,s[step].y=j,s[step].move=-1;
mo(i,j,-1);
dfs(step+1);
back(step);
s[step].x=0,s[step].y=0,s[step].move=0;
}
if (i+1<5 && mp[i+1][j]!=mp[i][j])//向右
{
s[step].x=i,s[step].y=j,s[step].move=1;
mo(i,j,1);
dfs(step+1);
back(step);
s[step].x=0,s[step].y=0,s[step].move=0;
}
}
}
}
void in()
{
int a;
for (int i=0;i<5;i++)//先是横坐标
for (int j=0;;j++)//后是纵坐标（注意这里有个坑）
{
scanf("%d",&a);
if(a) mp[i][j]=a;
else break;
}
}
int main()
{
scanf("%d",&n);
in();
dfs(1);
printf("-1");
return 0;
}
```
------------
# $\mathit{U\!pdate\;2\!0\!1\!9.9.1\!2}
军训时看到迷彩背心，突然想到一种更快的掉落方式。（心路历程：迷彩->一个个方块->开心消消乐->MAYAN游戏->更好的掉落方式）（我也不知道怎么想到的）
从每一列的最下方开始搜索，记录每个实体方块是这一列第几个，将它移到这个位置就可以了。
void drop()
{
for(int i=0;i<5;i++)
{
int c=0,m;
for(int j=0;j<7;j++)
{
if(mp[i][j])
m=mp[i][j],mp[i][j]=0,mp[i][c]=m,c++;
}
}
}
注意要将方块先清空并把颜色（数字）寄存到一个变量里，因为这个方法并不知道是不是没有掉落，而是寻找每个方块应该在的位置，如果后清理的话，就会出现没有移动的方块消失的情况。
这应该比循环找最下空方块快点吧（怎么感觉用时还变多了呢）