POJ 3126 Prime Path

【题意简述】：现给定两个四位素数，让我们从前一个素数变到后一个素数，而且变换过程中每次只能变一位，同时每次变化的结果都要是素数，并且在一组变换中不能出现同样的数，让我们现在求得这个变换的最小的次数！

【思路】：既然是最优的搜索问题，首先想到的就是BFS，所以，我们直接建立BFS的模型，通过队列去解决这个问题，详见代码：

代码借鉴：http://blog.csdn.net/wmn_wmn/article/details/7837723

//344K 0Ms
#include<iostream>
#include<cstdio>
#include<string.h>
#include<cmath>
#include<queue>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 10010;
int flag[N],visite[N];// flag 是素数标记 
					// visite是为了让每步所得素数不能重复！ 
int step[N];
int q,c,g,s;
void init()
{
	CLR(flag,0);
	for(int i = 2;i<=sqrt(N+0.5);++i)
	{
		if(!flag[i])
		{
			for(int j = i*2;j<N;j += i)
				flag[j] = 1;
		}
	}
}

void fun(int x)
{
	q = x / 1000;
	c = x%1000/100;
	s = x%100/10;
	g = x%10;
}

int fun2(int x,int y,int z,int w)
{
	return x*1000+y*100+z*10+w;
}

void bfs(int p1,int p2)
{
	queue<int> qq;
	qq.push(p1);
	visite[p1] = 1;
	step[p1]  = 0;
	while(1)
	{
		int x = qq.front();
		qq.pop();
		if(x == p2)
			break;
		fun(x);
		for(int i = 1;i<=9;i++)
		{
			int y = fun2(i,c,s,g);
			if(!flag[y]&&!visite[y])
			{
				qq.push(y);
				visite[y] = 1;
				step[y] = step[x] + 1;
			}
		}
		for(int i = 0;i <= 9; ++i){  
           int y = fun2(q,i,s,g);  
           if(!flag[y] && !visite[y]){  
               qq.push(y);  
               visite[y] = 1;  
               step[y] = step[x] + 1;  
           }  
        }
        for(int i = 0; i <= 9; ++i){  
           int y = fun2(q,c,i,g);  
           if(!flag[y] && !visite[y]){  
               qq.push(y);  
               visite[y] = 1;  
               step[y] = step[x] + 1;  
           }  
        }  
        for(int i = 0; i <= 9; ++i){  
           int y = fun2(q,c,s,i);  
           if(!flag[y] && !visite[y]){  
             qq.push(y);  
             visite[y] = 1;  
             step[y] = step[x] + 1;  
           }  
        }  
	}
}

int main()
{
	init();
	int t,a,b;
	cin>>t;
	while(t--)
	{
		cin>>a>>b;
		if(a == b)
		{
			cout<<"0"<<endl;
			continue;
		}
		CLR(step,0);
		CLR(visite,0);
		bfs(a,b);
		cout<<step[b]<<endl;
	}
	return 0;
}

POJ 3126 Prime Path,布布扣,bubuko.com

POJ 3126 Prime Path

原文：http://blog.csdn.net/u013749862/article/details/23202767