3126 Prime Path-白红宇

3126 Prime Path

阅读量：4206 次

发布时间：2019-05-26

本文共 1975 字，大约阅读时间需要 6 分钟。

使用visited[]数组来避免重复操作。

如何判断一个数为质数的函数。

int upper = i / 2;

int flag = 0;

for( j = 3; j < upper; j += 2 )

{

upper = i / j;

if( i % j == 0 )

{

flag = 1;

break;

}

if( flag == 0 )

number[i] = 1;

memset的用法。

/* 3126 Prime Path */#include 
   
    #include 
    
     #include 
     
      using namespace std;const int MAX = 10000;int number[MAX];int visited[MAX];struct Node{    int a;    int index;    Node(int _a, int _index):a(_a), index(_index) {}};void prime(){    memset( number, 0, sizeof(number) );    int i, j;    for( i = 1001; i < MAX; i += 2 )    {	int upper = i / 2;	int flag = 0;	for( j = 3; j < upper; j += 2 )	{	    upper = i / j;	    if( i % j == 0 )	    {		flag = 1;		break;	    }	}	if( flag == 0 )	    number[i] = 1;    }}int arrayToInt( int * a ){    return a[1] * 1000 + a[2] * 100 + a[3] * 10 + a[4];}void intToArray( int a, int *num ){    int k[5] = {	1000, 100, 10, 1    };    int i;    for( i = 1; i<= 4; i++ )    {	num[i] = a / k[ i - 1 ];	a = a % k[ i - 1 ];    }}int bfs( int p, int q ){    if( p == q )	return 0;    queue
      
        que;    int num1[5], num2[5];    int i, j;    intToArray( p, num1 );    intToArray( q, num2 );    Node start = Node(p, 0);    que.push( start );    memset( visited, 0, sizeof(visited) );    visited[p] = 1;    while( true )     {	Node temp = que.front();	int num[5];	intToArray( temp.a, num );	for( i = 1; i <= 4; i++ )	{	    int l = num[i];	    for( j = 0; j <= 9; j++ )		    {		if( l != j )		{		    num[i] = j;		    int a = arrayToInt( num ); 		    num[i] = l;		    if( number[a] == 1 && visited[a] == 0 )		    {			if( a == q )			{//			    cout << a << endl;			    return temp.index + 1;			}			else			{			    Node next = Node(a, temp.index+1);			    visited[a] = 1;//			    cout << a << endl;			    que.push( next );			}		    }		}	    }    	}	que.pop();    }}int main(){    prime();    int n;    cin >> n;    int i;    for( i = 0; i < n; i++ )    {	int p, q;	cin >> p >> q;	cout << bfs( p, q ) << endl;    }    return 0;}