NOIP 2011 Mayan游戏 大暴搜
2019-05-08 07:23:40来源:博客园 阅读 ()
题目链接:https://www.luogu.org/problemnew/show/P1312
我的第一篇题解!!
当然感谢ZAGER 的提示,他的链接https://www.cnblogs.com/ZAGER/p/9535526.html
这道题是一个大暴搜,真实考验了我的代码能力……
写函数是个好习惯,思路清晰明了。
分步骤
定义map[i][j]表示当前地图的情况,last[x][i][j]表示第x步时地图原貌,ans[x][i]记录第x步时的操作
check()检查是否被消完,当然根据规则只要检查最下面一行是否都被消完即可;
bool check() { for(int i=1;i<=5;i++) { if(map[i][1]) return 0; } return 1; }
update()进行掉落过程,我们从下往上搜,记录当前map有值的时候其下面有几个空行
void update()//掉落过程 { for(int i=1;i<=5;i++) { int down=0; for(int j=1;j<=7;j++) { if(!map[i][j]) down++; else { if(!down) continue; map[i][j-down]=map[i][j]; map[i][j]=0; } } } }
重点在这(对于我来说)
转换移动的操作,没好好看题,移动的时候不一定只和其他方块互换,也可以拖到悬空,然后掉落,所以互换后要检查掉落情况
void move(int x,int y,int z)//转换移动 { int mem=map[x][y]; map[x][y]=map[x+z][y]; map[x+z][y]=mem; update(); while(remove()) update();//被消除后进行掉落 }
remove()用来进行消除过程。为了满足条件图5情况,我们先记录在进行消除。
int remove()//消除过程 { bool flag=0; for(int i=1;i<=5;i++) { for(int j=1;j<=7;j++) { if(i>=2&&i<=4&&map[i][j]&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]) { xx[i-1][j]=1;xx[i][j]=1;xx[i+1][j]=1;flag=1; } if(j>=2&&j<=6&&map[i][j]&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]) { xx[i][j]=1;xx[i][j-1]=1;xx[i][j+1]=1;flag=1; } } }//先记录再消除,满足图五情况 if(!flag) return 0; for(int i=1;i<=5;i++) { for(int j=1;j<=7;j++) { if(xx[i][j]) { map[i][j]=0; xx[i][j]=0; } } } return 1; }
还有几个无关紧要(也很重要)的小函数,代码里有注解
还有一个重要的剪枝,就是“向左的时候如果左方并非是空,则跳过(否则可以选择其左侧方块右移,这样字典序更小)”;
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; int map[10][10],last[10][10][10],ans[10][5];//map当前地图,;last第几步移动前的地图;ans是前为步数,后为答案 int xx[10][10]; bool check() { for(int i=1;i<=5;i++) { if(map[i][1]) return 0; } return 1; } void memory(int x) { for(int i=1;i<=5;i++) { for(int j=1;j<=7;j++) { last[x][i][j]=map[i][j];//记录第x步时地图的原貌 } } } void update()//掉落过程 { for(int i=1;i<=5;i++) { int down=0; for(int j=1;j<=7;j++) { if(!map[i][j]) down++; else { if(!down) continue; map[i][j-down]=map[i][j]; map[i][j]=0; } } } } int remove()//消除过程 { bool flag=0; for(int i=1;i<=5;i++) { for(int j=1;j<=7;j++) { if(i>=2&&i<=4&&map[i][j]&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]) { xx[i-1][j]=1;xx[i][j]=1;xx[i+1][j]=1;flag=1; } if(j>=2&&j<=6&&map[i][j]&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]) { xx[i][j]=1;xx[i][j-1]=1;xx[i][j+1]=1;flag=1; } } }//先记录再消除,满足图五情况 if(!flag) return 0; for(int i=1;i<=5;i++) { for(int j=1;j<=7;j++) { if(xx[i][j]) { map[i][j]=0; xx[i][j]=0; } } } return 1; } void move(int x,int y,int z)//转换移动 { int mem=map[x][y]; map[x][y]=map[x+z][y]; map[x+z][y]=mem; update(); while(remove()) update();//被消除后进行掉落 } void recover(int x) { for(int i=1;i<=5;i++) { for(int j=1;j<=7;j++) { map[i][j]=last[x][i][j]; } } ans[x][1]=0;ans[x][2]=0;ans[x][3]=0; } void dfs(int x) { if(check()) { for(int i=1;i<=n;i++) { if(i!=1) printf("\n"); for(int j=1;j<=3;j++) { printf("%d ",ans[i][j]); } } exit(0); } if(x==n+1) return ; memory(x); for(int i=1;i<=5;i++) { for(int j=1;j<=7;j++) { if(map[i][j]) { if(i<=6&&map[i][j]!=map[i+1][j]) { move(i,j,1); ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1; dfs(x+1); recover(x);//恢复原地图和ans } } if(i>=2&&(!map[i-1][j])) { move(i,j,-1); ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1; dfs(x+1); recover(x); } } } } int main() { scanf("%d",&n); for(int i=1;i<=5;i++) { for(int j=1;j<=8;j++) { int x; scanf("%d",&x); if(x==0) break; map[i][j]=x; } } dfs(1);//从第一步开始搜 printf("-1\n"); return 0; }
原文链接:https://www.cnblogs.com/WHFF521/p/10827094.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 津津的储蓄计划 NOIp提高组2004 2020-04-01
- 【做题笔记】[NOIOJ,非NOIp原题]装箱问题 2020-02-14
- P2052 [NOI2011]道路修建 2019-10-29
- CSP(noip)中的简单对拍写法 2019-10-25
- NOIP模拟day1-T1(完全背包) 2019-10-12
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash