DFS／BFS 搜索训练

2019-11-06 08:11:50

字体：大中小

来源：转载

供稿：网友

hdu 1016：

#include <cstdio>#include <iostream>#include <cstring>using namespace std;int PRime[40]={0,0,1},vis[40],num[40],n;void checkPrime(){ for(int i=3;i<=40;i++){ prime[i]=1; for(int k=2;k<i;k++){ if(i%k==0){ prime[i]=0; break; } } }}void DFS(int i){ if(i==n+1) { printf("1"); for(int i=2;i<=n;i++) printf(" %d",num[i]); printf("/n"); return; } for(int c=2;c<=n;c++){ if(vis[c]==0 && prime[num[i-1]+c]){ if(i==n&&prime[c+1]!=1) return; vis[c]=1; num[i]=c; DFS(i+1); vis[c]=0; } }}int main(){ int t=0; checkPrime(); while(~scanf("%d",&n)){ printf("Case %d:/n",++t); memset(vis, 0, sizeof(vis)); memset(num, 0, sizeof(num)); vis[1]=1; num[1]=1; num[n+1]=1; DFS(2); printf("/n"); } return 0;}

POJ 1562

#include <cstdio>#include <cstdlib>#include <iostream>#include <cstring>using namespace std;int m,n,sum,vis[105][105];char map[105][105];int dx[3]={0,1,-1};int dy[3]={0,1,-1};void DFS(int x,int y,int f){ if(map[x][y]=='*' || vis[x][y]) return; if(f==0) sum++; vis[x][y]=1; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ int fx = x+dx[i]; int fy = y+dy[j]; if(fx>=0&&fx<m&&fy>=0&&fy<n&&map[fx][fy]=='@'){ DFS(fx,fy,1); } } }}int main(){ //freopen("cin.in", "r", stdin); while (~scanf("%d %d",&m,&n)&&m) { for(int i=0;i<m;i++) scanf("%s",map[i]); memset(vis, 0, sizeof(vis)); sum=0; for(int i=0;i<m;i++) for(int j=0;j<n;j++) if(map[i][j]=='@') DFS(i,j,0); printf("%d/n",sum); } return 0;}

这题有个难点是怎么判断是不是同一个油田，我选择在dfs里传入参数f，如果是通过遍历进入的f为0，通过dfs进入的为1，这样就很好的区分了油田。

HDU 1548

#include <cstdio>#include <iostream>#include <cstring>#include <queue>using namespace std;int N,START,END,step[205],vis[205];struct Node{ int num,step;};int BFS(){ Node node; node.num = START; node.step = 0; vis[START]=1; queue<Node> q; q.push(node); while (!q.empty()) { Node now =q.front(); q.pop(); if(now.num == END) return now.step; for(int i=-1;i<=1;i+=2){ Node s; s.num = now.num+i*step[now.num]; if(s.num>0&&vis[s.num]==0){ s.step = now.step+1; vis[s.num]=1; q.push(s); } } } return -1;}int main(){ while (~scanf("%d",&N)&&N) { scanf("%d%d",&START,&END); for(int i=1;i<=N;i++) scanf("%d",&step[i]); memset(vis, 0, sizeof(vis)); printf("%d/n",BFS()); } return 0;}

上一篇：install numpy

下一篇：区间质数

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注