本文主要是介绍【MOOC-浙大数据结构】第六周的编程作业——深搜广搜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.列出连通集
#include <stdio.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n,e;
int ma[15][15];
int vis[15];
void dfs(int x)
{vis[x]=1;printf("%d ",x);int i;for(i=0;i<n;i++){if(vis[i]==0){if(ma[x][i])dfs(i);}}
}
void bfs(int x)
{vis[x]=1;int i,y;queue<int> q;q.push(x);while(!q.empty()){y=q.front();q.pop();for(i=0;i<n;i++){if(ma[y][i]&&vis[i]==0){vis[i]=1;q.push(i);printf("%d ",i); }}}
}
int main()
{int i,x,y;memset(ma,0,sizeof ma);scanf("%d %d",&n,&e);for(i=0;i<e;i++){scanf("%d %d",&x,&y);ma[x][y]=ma[y][x]=1;}//dfs memset(vis,0,sizeof vis);for(i=0;i<n;i++){ if(vis[i]==0){printf("{ "); dfs(i);printf("}\n");} }//bfsmemset(vis,0,sizeof vis);for(i=0;i<n;i++){ if(vis[i]==0){printf("{ %d ",i); bfs(i);printf("}\n");} }
}2.Saving James Bond - Easy Version
因为他一开始在一个直径15的小岛上，所以起步第一跳的范围是d-7.5
#include <stdio.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
int n,d,flag;
int vis[105];
struct Position
{double x,y;
}position[105];
bool firstjump(int i)
{return (sqrt(position[i].x*position[i].x+position[i].y*position[i].y))<=(d+7.5);
}
bool jump(int v,int i)
{return sqrt(fabs(position[v].x-position[i].x)*fabs(position[v].x-position[i].x) +fabs(position[v].y-position[i].y)*fabs(position[v].y - position[i].y))<=d;
}
bool IsSave(int v)
{return (fabs(position[v].x)>=50-d||fabs(position[v].y)>=50-d);
}
void dfs(int x)
{ vis[x]=1;if(IsSave(x)) {//安全 flag=1;return;}int i;for(i=0;i<n;i++){if(vis[i]==0){if(jump(x,i)){dfs(i);}}}return;
}
int main()
{int i,x,y;flag=0;memset(vis,0,sizeof vis);scanf("%d %d",&n,&d);for(i=0;i<n;i++)scanf("%lf %lf",&position[i].x,&position[i].y);for(i=0;i<n;i++){if(vis[i]==0&&firstjump(i)){vis[i]=1;dfs(i);}}if(flag==0)printf("No\n");elseprintf("Yes\n");
}3.六度空间
用二维数组存图的话会内存超限，所以用Vector
#include <stdio.h>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
int n,e;
vector<int> ma[10005];
int vis[10005];
int bfs(int x)
{vis[x]=1;int count=1,tail,i;int level=0,last=x;queue<int> q;q.push(x);while(!q.empty()){int y=q.front();q.pop();for(i=0;i<ma[y].size();i++){if(vis[ma[y][i]]==0){vis[ma[y][i]]=1;q.push(ma[y][i]);count++;tail=ma[y][i];}}if(y==last){level++;last=tail;}if(level==6)break;}return count;
}
int main()
{int i,x,y;scanf("%d %d",&n,&e);for(i=0;i<e;i++){scanf("%d %d",&x,&y);ma[x].push_back(y);ma[y].push_back(x);}for(i=1;i<=n;i++){ memset(vis,0,sizeof vis);printf("%d: %.2lf%%\n",i,1.0*bfs(i)*100/n);}
}
这篇关于【MOOC-浙大数据结构】第六周的编程作业——深搜广搜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
