学步园

//广度优先搜索<br /> #include<iostream><br /> #include<queue><br /> using namespace std;<br /> const int SIZE = 10000;<br /> bool prime[SIZE];<br /> int step[SIZE];//树深度标志<br /> int base[4] = {1,10,100,1000};<br /> int main()<br /> {<br /> for(int i = 0; i < SIZE; i++) prime[i] = true;//生成素数表，方便判断<br /> for(int i = 2; i < SIZE; i++)<br /> {<br /> if(prime[i])<br /> {<br /> for(int j = 2; i*j < SIZE; j++)<br /> prime[i*j] = false;<br /> }<br /> }<br /> int t,a,b,d[4];<br /> cin >> t;<br /> while(t--)<br /> {<br /> cin >> a >> b;<br /> memset(step,0,sizeof(step));<br /> queue<int> path;//队列<br /> path.push(a);<br /> step[a] = 1;<br /> while(!path.empty())<br /> {<br /> int ori = path.front();<br /> if(ori == b)break;<br /> path.pop();<br /> //分离位数<br /> d[0] = ori%10;<br /> d[1] = ori%100/10;<br /> d[2] = ori%1000/100;<br /> d[3] = ori/1000;<br /> int newnum;//产生的新数<br /> for(int i = 0; i < 10; i ++)<br /> {<br /> newnum = ori - d[3]*1000 + i*1000;//枚举符合条件的数<br /> if(i != 0 && prime[newnum] && !step[newnum])//是质数且未假如队列<br /> {<br /> step[newnum] = step[ori] + 1;<br /> path.push(newnum);<br /> }<br /> for(int k = 0; k < 3; k++)<br /> {<br /> newnum = ori - d[k]*base[k] + i*base[k];<br /> if(prime[newnum] && !step[newnum])<br /> {<br /> step[newnum] = step[ori] + 1;//子节点在父亲节点的基础上深度增加1<br /> path.push(newnum); //假如队列<br /> }<br /> }<br /> }<br /> }<br /> cout << step[b] - 1 << endl;<br /> }<br /> return 0;<br /> }