数字变换(普及中级广搜最后一题)DEBUG

wwLucas  •  1个月前

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int n;
	int step;
};
const int N=100;
int vis[1000];
int flag[N];
void inti()
{
	for(int i=2;i<N;i++)
	{
		if(!flag[i])
		{
		    for(int j=2*i;j<N;j=j+i)	
		    {
		    	flag[j]=1;
			}
		}
	}
}
bool prime(int n)
{
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}
queue<node> q;
int bfs(int s,int t)
{
    inti();
	if(s==t)
	{
		return 0;
	}
	if(s==1)
	{
		return -1;
	}
	if(s>t)
	{
		return -1;
	}
	node e;
	e.n=s;
	e.step=0;
	q.push(e);
	while(!q.empty())
	{	
		node f;
		f=q.front();
		if(f.n==t)
	    {
	    	return f.step;
		}
		q.pop();
		node x=f;
		for(int i=2;i<f.n-1;i++)
		{
			if(flag[i]==0&&f.n%i==0)
			{
				f.n=f.n+i;
				f.step=f.step+1;
			}
	    }
	    if(x.n>t)
	    {
	    	return -1;
		}
		if(vis[x.n]==0)
		{
			q.push(x);
			vis[x.n]=1;
		}
	}
	return -1;
}
int main()
{
	int T,k=1;
	scanf("%d",&T);
	while(k<=T)
	{
		int n,s;
		scanf("%d%d",&n,&s);
		printf("Case %d: %d\n",k,bfs(n,s));
		k++;
	}
	return 0;
} 

暂未启用评论功能。