洛谷 P1312 NOIp2011提高组 Mayan游戏 题解【搜索】【模拟】
点击量：248
多存一个状态用来剪枝是好方法//按题意剪枝也是
题目描述
Mayan Puzzle 是最近流行起来的一个游戏。游戏界面是一个7行$ \times$5列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：
1 、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图6到图7）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1和图2）；
2 、任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图1到图3）。
注意：
a) 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图4，三个颜色为1的方块和三个颜色为2的方块会同时被消除，最后剩下一个颜色为2的方块）。
b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除（例如下面图5所示的情形，5个方块会同时被消除）。
3 、方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除。
上面图1到图3给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为(0,0)，将位于(3,3)的方块向左移动之后，游戏界面从图1变成图2所示的状态，此时在一竖列上有连续三块颜色为4的方块，满足消除条件，消除连续3块颜色为4的方块后，上方的颜色为3的方块掉落，形成图3所示的局面。
输入输出格式
输入格式：
共6行。
第一行为一个正整数$ n$，表示要求游戏通关的步数。
接下来的5行，描述$ 7\times 5$的游戏界面。每行若干个整数，每两个整数之间用一个空格隔开，每行以一个0结束，自下向上表示每竖列方块的颜色编号（颜色不多于10种，从1开始顺序编号，相同数字表示相同颜色）。
输入数据保证初始棋盘中没有可以消除的方块。
输出格式：
如果有解决方案，输出$ n$行，每行包含3个整数$ x,y,g$，表示一次移动，每两个整数之间用一个空格隔开，其中$ (x,y)$表示要移动的方块的坐标，$ g$表示移动的方向，1表示向右移动，-1表示向左移动。注意：多组解时，按照$ x$为第一关键字，$ y$为第二关键字，1优先于-1，给出一组字典序最小的解。游戏界面左下角的坐标为(0,0)。
如果没有解决方案，输出一行，包含一个整数-1。
输入输出样例
输入样例#1：3 1 0 2 1 0 2 3 4 0 3 1 0 2 4 3 4 0输出样例#1：2 1 1 3 1 1 3 0 1说明
【输入输出样例说明】
按箭头方向的顺序分别为图6到图11
样例输入的游戏局面如上面第一个图片所示，依次移动的三步是：(2,1)处的方格向右移动，(3,1)处的方格向右移动，(3,0)处的方格向右移动，最后可以将棋盘上所有方块消除。
【数据范围】
对于$ 30\%
的数据，初始棋盘上的方块都在棋盘的最下面一行；
对于$ 100\%
的数据，$ 0\le n\le 5$。
题解：
只要按题目意思来，搜到的第一个就是最优解。不过这个题搜索的回溯过程很难做，因此要在每一层存储一个数组，回溯时只能恢复原数组，这一点细节要注意。
输入数据是按列输的，因此要注意数组的方向。而且必须在满足刚好为$ n$的步数来，因此可能会出现交换两个相同的来浪费一步以达成刚好$ n$步的效果。
这个题主要的工作是由函数来完成的。一旦发现可以消除，就消除，然后下滑。下滑后如果还有可消除的就继续消除，因为不知道什么时候停止，所以用一个while。同时我们存一个tot表示现在还剩多少个方块，用clo[]存某种颜色还有多少种方块。如果某种颜色的方块数在(0,3)之间，那么它就无论如何也不能被消掉，提前剪枝。
虽然我们根据题意可以很好地“剪枝”，但是还是要注意几点：两个相邻位置上如果都有数，那么只管左边的数右移而不管右边的数左移，因为这样在两个方面上都会更优；而如果一个数左边或右边没有数，就可以把它抽到左边或右边去下滑，接着做下一步。
最近几次老犯的一个错误：发现一个错误，在主函数进入DFS时改掉了，但是在DFS函数里没有改。
解决方法：多次提醒自己这里有坑/把主函数里的那部分直接写到dfs中，主函数什么都不管直接调用dfs，让dfs去做第一步的判断。
Code：
#include<cstdio>
#include<cstring>
int n,tt=0;
int a[10][10],f[10][10][10];
int clo[12];
int ansx[10],ansy[10],ansd[10];
int flag=0;
void change(int num,int lx,int ly,int rx,int ry)//交换相邻两个数
{
int t=f[num][lx][ly];
f[num][lx][ly]=f[num][rx][ry];
f[num][rx][ry]=t;
}
int tag[10][10];
bool check(int num)//看有没有能消的，如果有就打tag
{
memset(tag,0,sizeof(tag));
int k=0,tmp=0;
for(int i=0;i<=4;i++)
for(int j=0;j<=6;j++)
if(f[num][i][j]==f[num][i][j-1]&&f[num][i][j]!=0)
{
k++;
if(k==2)
{
tmp=1;
tag[i][j]=1;
tag[i][j-1]=1;
tag[i][j-2]=1;
}
if(k>2)
tag[i][j]=1;
}
else
k=0;
for(int j=0;j<=6;j++)
for(int i=0;i<=4;i++)
if(f[num][i][j]==f[num][i-1][j]&&f[num][i][j]!=0)
{
k++;
if(k==2)
{
tmp=1;
tag[i][j]=1;
tag[i-1][j]=1;
tag[i-2][j]=1;
}
if(k>2)
tag[i][j]=1;
}
else
k=0;
return tmp;
}
void down(int num)//下滑
{
for(int i=0;i<=4;i++)
for(int j=0;j<=6;j++)
{
int u=j;
while(u&&f[num][i][u-1]==0)//warning
{
f[num][i][u-1]=f[num][i][u];
f[num][i][u]=0;
u--;
}
}
}
void Clear(int num)//消除
{
for(int i=0;i<=4;i++)
for(int j=0;j<=6;j++)
if(tag[i][j])
{
tt--;
clo[f[num][i][j]]--;
f[num][i][j]=0;
}
down(num);
}
int t=0;
void dfs(int num)
{
down(num-1);//注意下滑，因为可能有刚被抽出来悬空的方块
int sav[10][10];
int savc[12];
for(int i=1;i<=10;i++)
savc[i]=clo[i];
while(check(num-1))//消除直到不能消除为止
Clear(num-1);
for(int i=1;i<=10;i++)
if(clo[i]==1||clo[i]==2)
return;
for(int i=0;i<=4;i++)
for(int j=0;j<=6;j++)
sav[i][j]=f[num-1][i][j];
if(num==n)//必须刚好n步
{
if(tt==0)
flag=1;
return;
}
int savtt=tt;
for(int i=0;i<=4;i++)
for(int j=0;j<=6;j++)//枚举每个点
{
for(int u=0;u<=4;u++)
for(int v=0;v<=6;v++)
f[num][u][v]=sav[u][v];//恢复每个点的状态
for(int i=1;i<=10;i++)
clo[i]=savc[i];
tt=savtt;
if(f[num][i][j]>0&&i<4)
{
change(num,i,j,i+1,j);
dfs(num+1);
if(flag)
{
ansx[num]=i;
ansy[num]=j;
ansd[num]=1;
return;
}
for(int u=0;u<=4;u++)
for(int v=0;v<=6;v++)
f[num][u][v]=sav[u][v];
for(int i=1;i<=10;i++)
clo[i]=savc[i];
}
tt=savtt;
if(f[num][i][j]>0&&i>0&&f[num][i-1][j]==0)
{
change(num,i,j,i-1,j);
dfs(num+1);
if(flag)
{
ansx[num]=i;
ansy[num]=j;
ansd[num]=-1;
return;
}
}
}
}
int main()
{
int u;
scanf("%d",&n);
for(int i=0;i<=4;i++)
{
int cnt=0;
scanf("%d",&a[i][cnt++]);
clo[a[i][cnt-1]]++;
while(a[i][cnt-1]!=0)
{
tt++;
scanf("%d",&a[i][cnt++]);
clo[a[i][cnt-1]]++;
}
cnt--;
}
int savtt=tt;///这些sav都是存一开始的数据
int sav[10][10];
int savc[12];
for(int i=1;i<=10;i++)
savc[i]=clo[i];
for(int i=0;i<=4;i++)
for(int j=0;j<=6;j++)
sav[i][j]=a[i][j];
for(int i=0;i<=4;i++)
for(int j=0;j<=6;j++)
{
if(sav[i][j]==0)
continue;
for(int i=1;i<=10;i++)//每次更新
clo[i]=savc[i];
for(int u=0;u<=4;u++)
for(int v=0;v<=6;v++)
f[0][u][v]=sav[u][v];
if(f[0][i][j]>0&&i<4)//最后一列不能右移
{
tt=savtt;
change(0,i,j,i+1,j);
dfs(1);
if(flag)//一搜到就输出答案
{
ansx[0]=i;//输出答案
ansy[0]=j;
ansd[0]=1;
for(int k=0;k<n;k++)
printf("%d %d %d\n",ansx[k],ansy[k],ansd[k]);
return 0;
}
for(int i=1;i<=10;i++)
clo[i]=savc[i];
for(int u=0;u<=4;u++)
for(int v=0;v<=6;v++)
f[0][u][v]=sav[u][v];
}
if(f[0][i][j]>0&&i>0&&f[0][i-1][j]==0)
{
tt=savtt;
change(0,i,j,i-1,j);
dfs(1);
if(flag)
{
ansx[0]=i;
ansy[0]=j;
ansd[0]=-1;
for(int k=0;k<n;k++)
printf("%d %d %d\n",ansx[k],ansy[k],ansd[k]);
return 0;
}
}
}
puts("-1");
return 0;
}
… [Trackback]
[…] Read More Information here to that Topic: wjyyy.top/1183.html […]
… [Trackback]
[…] Read More here on that Topic: wjyyy.top/1183.html […]