题解 P1312 【Mayan游戏】
看了一圈题解，发现好像没有bfs的题解
这几天新算法学的有点疲，看到数论又不想做，所以决定写一点暴力的题目回回神
首先，这题一看肯定是个暴力搜索，因为题目中的变换/操作略复杂，所以我们尽量分开写函数解决每块小操作
注：本文中的地图变量 [ i ][ j ] 均代表自下而上第i行，自左而右第j列
首先把图用二维数组表示出来，结构体，图方便
struct node{int pad[10][10];}题目中总共满足三个操作：
1.掉落
当一个方块下方没有方块时，会往下掉，直到到底或下方有方块
实现[x][y]方块的掉落
void drop(int x,int y,node &u){ //同步修改掉，用地址，下同
int r=x; //用来记录当前掉落块，接下来有用
if(u.pad[x][y]==0)return; //如果是个“空块”，不做了
bool flag=0; //用来判定这个块有没有掉落
while(u.pad[x-1][y]==0&&x>0)//下方为空且不是最底层
{
flag=1;
swap(u.pad[x-1][y],u.pad[x][y]);//掉落即交换
x--; //自己的位置降低
}
if(flag)drop(r+1,y,u); //如果自己掉了，自己上方也掉
}2.横向拖动/交换
每个方块可以向左/右拖动，即与左/右交换方块，于是我们可以用简单的swap搞定
void move(int x,int y,int d,node &u){
swap(u.pad[x][y],u.pad[x][y+d]);//d是方向即1或-1，直接拿来用
drop(x+1,y,u);drop(x,y+d,u); //换来的可能是 0 ，换出去的一定不是零，会在宽搜时候保证
//我的上方方块可能会掉落，我过去的地方可能会使我掉落
}3.消除
横向或纵向的三个连续相同块可以消掉，且可以共用块
因为有了共用块的性质，所以肯定不能无脑找到就消除，不妨打标记
void del(node &u){
bool need=0;
memset(vis,0,sizeof(vis)); //vis数组用来打标记
for(int i=0;i<7;i++) //从左下往右上搜
for(int j=0;j<5;j++) //只要考虑向右和向上的连续块即可
if(u.pad[i][j]!=0){ //存在方块
if(u.pad[i+1][j]==u.pad[i][j]&&u.pad[i+2][j]==u.pad[i][j])//纵向三个相连
vis[i][j]=vis[i+1][j]=vis[i+2][j]=1;
if(u.pad[i][j+1]==u.pad[i][j]&&u.pad[i][j+2]==u.pad[i][j])//横向三个相连
vis[i][j]=vis[i][j+1]=vis[i][j+2]=1;
}
for(int i=6;i>=0;i--) //消除的时候从上往下，可以同步drop操作
for(int j=0;j<5;j++)
if(vis[i][j]){ //被标记了要消除
u.pad[i][j]=0; //消掉
drop(i+1,j,u); //上方的方块下落
need=1;
}
if(need)del(u);
}Tip：
1.消除的时候从上往下消，相信可以感性理解
2.可能会有疑问，need有啥用，看我们的强力样例
如果我们只扫一遍，会剩下这么个玩意
所以我们用一个need来判定有没有消除，如果有消除，那么再扫一遍，看在掉落后有没有新的可以消除的块
--------------------------------------------------------------------- 华丽丽的分割线
所有的操作解决，要消除完毕才算完成
一个check解决
bool check(node u){
for(int i=0;i<7;i++)
for(int j=0;j<5;j++)
if(u.pad[i][j]!=0)return false;//还有方块，失败
return true;
}所有该有的操作和性质都搞定，来个宽搜的板子套一下！ 上代码
#include<bits/stdc++.h>
using namespace std;
struct node{int pad[10][10];}s;
struct point{
node ground;
int step,mx[10],my[10],dir[10];//步数，x选择，y选择，方向
};
queue<point>line;
int n,a,cnt[5];
bool vis[10][10],flag;
bool check(node u){
for(int i=0;i<7;i++)
for(int j=0;j<5;j++)
if(u.pad[i][j]!=0)return 0;
return 1;
}
void drop(int x,int y,node &u){
int r=x;
if(u.pad[x][y]==0)return;
bool flag=1;
while(u.pad[x-1][y]==0&&x>0)
{
flag=1;
u.pad[x-1][y]=u.pad[x][y];
u.pad[x][y]=0;
x--;
}
if(flag)drop(r+1,y,u);
}
void del(node &u){
bool need=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<7;i++)
for(int j=0;j<5;j++)
if(u.pad[i][j]!=0){
if(u.pad[i+1][j]==u.pad[i][j]&&u.pad[i+2][j]==u.pad[i][j])
vis[i][j]=vis[i+1][j]=vis[i+2][j]=1;
if(u.pad[i][j+1]==u.pad[i][j]&&u.pad[i][j+2]==u.pad[i][j])
vis[i][j]=vis[i][j+1]=vis[i][j+2]=1;
}
for(int i=6;i>=0;i--)
for(int j=0;j<5;j++)
if(vis[i][j]){
u.pad[i][j]=0;
drop(i+1,j,u);
need=1;
}
if(need)del(u);
}
void move(int x,int y,int d,node &u){
swap(u.pad[x][y],u.pad[x][y+d]);
drop(x+1,y,u);drop(x,y+d,u);//换来的可能是 0 ，换出去的一定不是零
}
void bfs(){
point e;
e.ground=s;
e.step=0;
line.push(e);
while(!line.empty())
{
point u=line.front(),v;
line.pop();
node back=u.ground;
for(int j=0;j<5;j++)
for(int i=0;i<7;i++)
{
if(back.pad[i][j]!=0)/显然，只有有方块的进行拖动是有效的
{
if(j+1<5){//判定右移合法
v=u;v.step++;
v.mx[v.step]=j,v.my[v.step]=i;
v.dir[v.step]=1;
move(i,j,1,v.ground);
del(v.ground);
if(v.step<n){line.push(v);}
if(v.step==n&&check(v.ground)){
for(int k=1;k<=n;k++)
cout<<v.mx[k]<<" "<<v.my[k]<<" "<<v.dir[k]<<endl;
flag=1;
return ;
}
}
if(j-1>=0){//左移合法
v=u;v.step++;
v.mx[v.step]=j,v.my[v.step]=i;
v.dir[v.step]=-1;
move(i,j,-1,v.ground);
del(v.ground);
if(v.step<n){line.push(v);}
if(v.step==n&&check(v.ground)){
for(int k=1;k<=n;k++)
cout<<v.mx[k]<<" "<<v.my[k]<<" "<<v.dir[k]<<endl;
flag=1;
return ;
}
}
}
}
}
return ;
}
int main(){
cin>>n;
for(int i=0;i<=4;i++)
{
while(cin>>a)
{
if(!a)break;
s.pad[cnt[i]++][i]=a;
}
}
bfs();
if(!flag)printf("-1");
return 0;
}
大功告成！！！
然鹅50pts.....
MLE+TLE
回头再看看我们的代码
bfs也太裸了！！！
70pts：
我会剪枝！！！
我们发现，在左右两个都有的情况下，左边块右移和右边块左移是一样的！
所以，在向左移动时可以判一下，只有左边为空的时候移动，减少状态量！！！
还剩三个MLE
90pts：
我会 卡空间！！！
我们的node结构体里开了10 10的数组，完全可以只开8 8嘛,point里最多n只有5，缩到6不就好了？
又是一发，然而还是MLE
100pts：
我会 继续卡空间！！！
我们的结构体里存的数最大不超过10
short大法吼啊
不过，仅限此题数据小，只要数据加强，不一定卡的过去
真·100pts:
我会 判重 重载运算符！！！
STL库，map函数好啊！
当然，map里其实是一棵红黑树，所以我们要重载小于运算符！毕竟我们的检索需要进行比较
下面是正经的AC代码，没啥注释，码风丑陋，见谅
#include<bits/stdc++.h>
using namespace std;
int n,a,cnt[5];
bool vis[8][8],flag;
struct node{
short pad[8][8];
bool operator < (const node &a)const
{
for(int i(0);i < 7;++i)
for(int j(0);j < 5;++j){
if(pad[i][j] != a.pad[i][j])return pad[i][j] < a.pad[i][j];
}
return false;
}//重载运算符
}s;
struct point{
node ground;
short step,mx[6],my[6];
int dir[6];
};
queue<point>line;
bool check(node u){
for(int i=0;i<7;i++)
for(int j=0;j<5;j++)
if(u.pad[i][j]!=0)return 0;
return 1;
}
void drop(int x,int y,node &u){
int r=x;
if(u.pad[x][y]==0)return;
bool flag=1;
while(u.pad[x-1][y]==0&&x>0)
{
flag=1;
u.pad[x-1][y]=u.pad[x][y];
u.pad[x][y]=0;
x--;
}
if(flag)drop(r+1,y,u);
}
void del(node &u){
bool need=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<7;i++)
for(int j=0;j<5;j++)
if(u.pad[i][j]!=0){
if(u.pad[i+1][j]==u.pad[i][j]&&u.pad[i+2][j]==u.pad[i][j])
vis[i][j]=vis[i+1][j]=vis[i+2][j]=1;
if(u.pad[i][j+1]==u.pad[i][j]&&u.pad[i][j+2]==u.pad[i][j])
vis[i][j]=vis[i][j+1]=vis[i][j+2]=1;
}
for(int i=6;i>=0;i--)
for(int j=0;j<5;j++)
if(vis[i][j]){
u.pad[i][j]=0;
drop(i+1,j,u);
need=1;
}
if(need)del(u);
}
void move(int x,int y,int d,node &u){
swap(u.pad[x][y],u.pad[x][y+d]);
drop(x+1,y,u);drop(x,y+d,u);//换来的可能是 0 ，换出去的一定不是零
}
void bfs(){
map<node,bool>used;
used[s]=1;
point e;
e.ground=s;
e.step=0;
line.push(e);
while(!line.empty())
{
point u=line.front(),v;
line.pop();
node back=u.ground;
for(int j=0;j<5;j++)
for(int i=0;i<7;i++)
{
if(back.pad[i][j]!=0)
{
if(j+1<5){
v=u;v.step++;
v.mx[v.step]=j,v.my[v.step]=i;//注意，这里记录的时候是按输出要求的x、y记录的，和原先定义的恰好相反
v.dir[v.step]=1;
move(i,j,1,v.ground);
del(v.ground);
if(v.step<n&&!used[v.ground]){line.push(v);used[v.ground]=1;}
if(v.step==n&&check(v.ground)){
for(int k=1;k<=n;k++)
cout<<v.mx[k]<<" "<<v.my[k]<<" "<<v.dir[k]<<endl;
flag=1;
return ;
}
}
if(j-1>=0&&back.pad[i][j-1]==0){
v=u;v.step++;
v.mx[v.step]=j,v.my[v.step]=i;
v.dir[v.step]=-1;
move(i,j,-1,v.ground);
del(v.ground);
if(v.step<n&&!used[v.ground]){line.push(v);used[v.ground]=1;}
if(v.step==n&&check(v.ground)){
for(int k=1;k<=n;k++)
cout<<v.mx[k]<<" "<<v.my[k]<<" "<<v.dir[k]<<endl;
flag=1;
return ;
}
}
}
}
}
return ;
}
int main(){
cin>>n;
for(int i=0;i<=4;i++)
{
while(cin>>a)
{
if(!a)break;
s.pad[cnt[i]++][i]=a;
}
}
bfs();
if(!flag)printf("-1");
return 0;
}