【MOOC-浙大数据结构】第六周的编程作业——深搜&广搜

绝地灬酷狼 2021-11-10 15:24 269阅读 0赞

1.**[列出连通集][Link 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");
    		}	
    	}
    	//bfs
    	memset(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");
    	else
    	printf("Yes\n");
    }

3.**[六度空间][Link 2]**

用二维数组存图的话会内存超限，所以用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);
    	}
    }

[Link 1]: https://pintia.cn/problem-sets/1134360184290500608/problems/1148773762207969280
[Saving James Bond - Easy Version]: https://pintia.cn/problem-sets/1134360184290500608/problems/1148773762207969281
[Link 2]: https://pintia.cn/problem-sets/1134360184290500608/problems/1148773762207969282