资料来源:BFS-DFS
图示来源:DFS;http://sjjg.js.zwu.edu.cn/SFXX/sf1/sdyxbl.html
BFS:http://sjjg.js.zwu.edu.cn/SFXX/sf1/gdyxbl.html
DFS(深度搜索)
DFS是从一个方向一搜到底,不满足条件即返回一层,搜这一层的其他的枝层。
#include<stdio.h>
int x,y;
int max=6;
int pan(int a,int b)
{
if(a>=0&&a<8&&b>=0&&b<8)
return 1;
return 0;
}
void dfs(int a,int b,int sum)
{
if(sum>=max)
return ;
if(a==x&&b==y&&sum<max)
{
max=sum;
return ;
}
if(pan(a+2,b+1))dfs(a+2,b+1,sum+1);
if(pan(a+2,b-1))dfs(a+2,b-1,sum+1);
if(pan(a-2,b-1))dfs(a-2,b-1,sum+1);
if(pan(a-2,b+1))dfs(a-2,b+1,sum+1);
if(pan(a-1,b-2))dfs(a-1,b-2,sum+1);
if(pan(a-1,b+2))dfs(a-1,b+2,sum+1);
if(pan(a+1,b-2))dfs(a+1,b-2,sum+1);
if(pan(a+1,b+2))dfs(a+1,b+2,sum+1);
}
int main()
{
int x1,y1;
char str1[100],str2[100];
while(scanf("%s%s",str1,str2)!=EOF)
{
max=6;
x1=str1[0]-'a';y1=str1[1]-'1';
x=str2[0]-'a';y=str2[1]-'1';
dfs(x1,y1,0);
printf("To get from %s to %s takes %d knight moves.\n",str1,str2,max);
}
return 0;
}
BFS(广度搜索)
BFS是对起点周围的点进行访问,然后慢慢的往外扩散,尤其实用与求最短路径问题。
#include<stdio.h>
#include<string.h>
struct list
{
int l;
int r;
int c;
int depth;
}first,last,qun[30000],pan;
int min;
int map[50][50][50];
int get(char c)
{
if(c=='.')
return 1;
if(c=='S')
return 2;
if(c=='E')
return 3;
return 0;
}
int bfs(int x,int y,int z)
{
int head,tail;
int visit[50][50][50];
memset(visit,1,sizeof(visit));
head=0;
tail=0;
qun[0].l=x;
qun[0].r=y;
qun[0].c=z;
qun[0].depth=1;
tail++;
visit[x][y][z]=0;
while(tail>head)
{
pan=qun[head];
head++;
if(pan.l==last.l&&pan.r==last.r&&pan.c==last.c)
{
min=pan.depth;
return 1;
}
if(map[pan.l-1][pan.r][pan.c]&&visit[pan.l-1][pan.r][pan.c])
{
visit[pan.l-1][pan.r][pan.c]=0;
qun[tail].l=pan.l-1;
qun[tail].r=pan.r;
qun[tail].c=pan.c;
qun[tail].depth=pan.depth+1;
tail++;
}
if(map[pan.l][pan.r-1][pan.c]&&visit[pan.l][pan.r-1][pan.c])
{
visit[pan.l][pan.r-1][pan.c]=0;
qun[tail].l=pan.l;
qun[tail].r=pan.r-1;
qun[tail].c=pan.c;
qun[tail].depth=pan.depth+1;
tail++;
}
if(map[pan.l][pan.r][pan.c-1]&&visit[pan.l][pan.r][pan.c-1])
{
visit[pan.l][pan.r][pan.c-1]=0;
qun[tail].l=pan.l;
qun[tail].r=pan.r;
qun[tail].c=pan.c-1;
qun[tail].depth=pan.depth+1;
tail++;
}
if(map[pan.l+1][pan.r][pan.c]&&visit[pan.l+1][pan.r][pan.c])
{
visit[pan.l+1][pan.r][pan.c]=0;
qun[tail].l=pan.l+1;
qun[tail].r=pan.r;
qun[tail].c=pan.c;
qun[tail].depth=pan.depth+1;
tail++;
}
if(map[pan.l][pan.r+1][pan.c]&&visit[pan.l][pan.r+1][pan.c])
{
visit[pan.l][pan.r+1][pan.c]=0;
qun[tail].l=pan.l;
qun[tail].r=pan.r+1;
qun[tail].c=pan.c;
qun[tail].depth=pan.depth+1;
tail++;
}
if(map[pan.l][pan.r][pan.c+1]&&visit[pan.l][pan.r][pan.c+1])
{
visit[pan.l][pan.r][pan.c+1]=0;
qun[tail].l=pan.l;
qun[tail].r=pan.r;
qun[tail].c=pan.c+1;
qun[tail].depth=pan.depth+1;
tail++;
}
}
return 0;
}
int main()
{
int l,r,c,t,i,j,s;
char str[50];
while(scanf("%d%d%d%*c",&l,&r,&c)&&(l||r||c))
{
memset(map,0,sizeof(map));
for(t=1;t<=l;t++)
{
for(i=1;i<=r;i++)
{
gets(str);
for(j=1;j<=c;j++)
{
s=get(str[j-1]);
if(s)map[t][i][j]=1;
if(s==2)
{
first.l=t;
first.r=i;
first.c=j;
}
if(s==3)
{
last.l=t;
last.r=i;
last.c=j;
}
}
}
if(t!=l)
getchar();
}
if(bfs(first.l,first.r,first.c))
{
printf("Escaped in %d minute(s).\n",min-1);
}
else
{
printf("Trapped!\n");
}
}
return 0;
}
今天的文章BFS-DFS分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/63090.html