第十一届蓝桥杯 国赛E.本质上升序列
2022/4/8 23:19:58
本文主要是介绍第十一届蓝桥杯 国赛E.本质上升序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
答案为:552
跳过恶心的D题,发现E题其实是一道标准的dfs。首先玩具蛇的头可以放在任意点上,循环遍历,将头部坐标入栈。处理好头部后,dfs分别看栈顶元素右左下上连接的点是否可达且未访问过,如果满足要求加入栈中,继续dfs。如果栈中已经有16个元素,即z[0]==16,那么说明玩具蛇的每一节已经全部放入盒中,将ans+1,回溯寻找其他的方案。
#include<stdio.h> #include<string.h> int map[10][10]; int z[20],ans; bool judge(int x,int y) { if(x>=1&&y>=1&&x<=4&&y<=4&&map[x][y]==0)return 1; return 0; } void prin() { printf("\n"); for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) { printf("%d ",map[i][j]); } printf("\n"); } } void dfs(); void go(int x,int y,int a) { map[x][y]=a; z[0]++;z[z[0]]=x*100+y; dfs(); map[x][y]=0; z[z[0]]=0;z[0]--; } void dfs() { if(z[0]==16) { ans++; //prin(); return; } int x=z[z[0]]/100,y=z[z[0]]%100; if(judge(x,y+1))go(x,y+1,map[x][y]+1); if(judge(x,y-1))go(x,y-1,map[x][y]+1); if(judge(x+1,y))go(x+1,y,map[x][y]+1); if(judge(x-1,y))go(x-1,y,map[x][y]+1); } int main() { for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) { memset(map,0,sizeof(map)); map[i][j]=1; z[0]=1; z[z[0]]=i*100+j; dfs(); z[z[0]]=0;z[0]--; } } printf("%d",ans); return 0; }
这篇关于第十一届蓝桥杯 国赛E.本质上升序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?