POJ - 3126 - Prime Path（BFS)

Prime Path

POJ - 3126

题意：

给出两个四位素数 a , b。然后从a开始，每次可以改变四位中的一位数字，变成 c，c 可以接着变，直到变成b为止。要求 c 必须是素数。求变换次数的最小值。（a,b,c都是四位数字，输入时没有前导零）

分析：

• 每次改变可以获得一个四位数c，然后如果c是素数并且之前没有出现过，那么我们把它放入队列即可。

int f[10001];

int v[10001];

void init()//素数筛

{

	memset(f,0,sizeof f);

	for(int i=2;i<=10000;i++)

	{

		if(f[i]==0)

		{

			for(int j = i+i;j<=10000;j+=i)

			{

				f[j] = 1;

			}

		}

	}

}

int a,b;

int bfs()

{

	memset(v,0,sizeof v);

	queue<int> q;

	q.push(a);

	v[a] = 1;

	int tmp;

	while(!q.empty())

	{

		tmp = q.front();q.pop();

		if(tmp==b)return v[tmp];

		int now;

		int t = v[tmp]+1;

		for(int i=0;i<=9;i++)//循环改变的数字 0 ~ 9

		{

			now = tmp - tmp%10+i;//改变个位

			if(now>=1000&&f[now]==0&&v[now] == 0){v[now] = t;q.push(now);}

			now = tmp/100*100+i*10+tmp%10;//改变十位

			if(now>=1000&&f[now]==0&&v[now] == 0){v[now] = t;q.push(now);}

			now = tmp/1000*1000+i*100+tmp%100;//改变百位

			if(now>=1000&&f[now]==0&&v[now] == 0){v[now] = t;q.push(now);}

			now = i*1000+tmp%1000;//改变千位

			if(now>=1000&&f[now]==0&&v[now] == 0){v[now] = t;q.push(now);}

		}

	}

}

int main()

{

    init();

    int T;cin>>T;

    while(T--)

    {

    	cin>>a>>b;

    	int ans = bfs();

    	cout<<ans-1<<endl;

    }

    return 0;

}