首页 > 代码库 > HDU 1976 prime path
HDU 1976 prime path
题意:给你2个数n m,从n变成m最少需要改变多少次。
其中:
1、n m 都是4位数
2、每次只能改变n的一个位数(个位、十位、百位、千位),且每次改变后后的新数为素数
思路:搜索的变形题,这次我们要搜得方向是改变位数中的一位,然后往下搜,直到求出我们需要的那个解
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> using namespace std; #define N 10000 int dis[N],cou[N]; bool prime[N]; void make() //素数打表 { int i,j; for(i=1000;i<=N;i++) { int flag=1; for(j=2;j<i/2;j++) { if(i%j==0) { prime[i]=false; flag=0; break; } } if(flag)prime[i]=true; } } int bfs(int x,int y) { queue <int>q; int v,i,j,temp,vtemp,t[4]; //t数组存放该数的每一位数 memset(dis,0,sizeof(dis)); memset(cou,0,sizeof(cou)); q.push(x); dis[x]=1; while(!q.empty()) { v=q.front(); q.pop(); t[0]=v/1000; t[1]=v%1000/100; t[2]=v%100/10; t[3]=v%10; for(j=0;j<4;j++) { temp=t[j]; for(i=0;i<10;i++) if(i!=temp) { t[j]=i; vtemp=t[0]*1000+t[1]*100+t[2]*10+t[3]; if(!dis[vtemp]&&prime[vtemp]){ cou[vtemp]=cou[v]+1; dis[vtemp]=1; q.push(vtemp); } if(vtemp==y) return cou[vtemp]; } t[j]=temp; } if(v==y) return cou[v]; } return -1; } int main() { int t,n,m,sum; make(); scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); sum=bfs(n,m); printf("%d\n",sum); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。