欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

ACM 深搜 SeedingTempter of the Bone

发布时间:2024/5/15 编程问答 3 豆豆
如意编程网 收集整理的这篇文章主要介绍了 ACM 深搜 SeedingTempter of the Bone 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

暑期集训开始啦~因为是第一天,所以还没有正式开始讲座什么的,下午是一个小训练。

题目主要是深搜广搜,难度不大,但是我为了以后日更垫个底,先更两题深搜压压惊~

 

ZOJ 2100 Seeding

题目大意:S是不能走得,剩下的.要一笔画完,问是否可以实现。

我的思路:一本正经的深搜啊,都写在备注里啦~

 

#include <stdio.h> char a[10][10]; int n,m,i,j,z[4][2]={0,1,0,-1,1,0,-1,0},re,sum;//四个方向 void dfs(int x,int y,int ss) {if(x>=n||y>=m||x<0||y<0)return;//出界 int i,xx,yy;for(i=0;i<4;i++){xx=x+z[i][0];yy=y+z[i][1];if(a[xx][yy]!='S'){if(ss==n*m-sum-1)//走完啦~ {re=1;return;}a[xx][yy]='S';//标记 dfs(xx,yy,ss+1);a[xx][yy]='.';//复原,方便下次深搜 }}return; } int main() { while(scanf("%d%d",&n,&m)){sum=0;if(n==0&&m==0)break;for(i=0;i<n;i++){scanf("%s",a[i]);for(j=0;j<m;j++){if(a[i][j]=='S')sum++;}}a[0][0]='S';re=0;dfs(0,0,0); if(re)printf("YES\n");else printf("NO\n");} }

 

 

ZOJ 2110 Tempter of the Bone 

 

 

题目大意:(参照样例一)给出4*4的地图,从S走到D,5步是否恰好可以,是正好五步,所以可以绕完为了满足这个5的哦。

我的思路:还是 一本正经 的 深搜呀...不过这里剪枝了一下,更快一些,深搜的函数里也可以剪。

 

#include <stdio.h> char a[10][10]; int n,m,s,i,j,z[4][2]={0,1,0,-1,1,0,-1,0},sx,sy,dx,dy,wall,re;//四个方向 void dfs(int x,int y,int ss) {if(x>=n||y>=m||x<0||y<0)return;//出界 if(ss==s&&x==dx&&y==dy) re=1;//走到目的地 if(re)return;int i,xx,yy;for(i=0;i<4;i++){xx=x+z[i][0];yy=y+z[i][1];if(a[xx][yy]!='X'){a[xx][yy]='X';//标记 dfs(xx,yy,ss+1);a[xx][yy]='.';//复原 }}return; } int main() { while(scanf("%d%d%d",&n,&m,&s)){wall=0;if(n==0&&m==0&&s==0)break;for(i=0;i<n;i++){scanf("%s",a[i]);for(j=0;j<m;j++){ if(a[i][j]=='S')sx=i,sy=j;if(a[i][j]=='D')dx=i,dy=j;if(a[i][j]=='X')wall++;}}if(n*m-wall<=s){printf("NO\n");continue;}a[sx][sy]='X';re=0;dfs(sx,sy,0); if(re)printf("YES\n");else printf("NO\n");} }

 

 

 

 

 

 

 

总结

以上是如意编程网为你收集整理的ACM 深搜 SeedingTempter of the Bone的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。