poj 3126 Prime Path (bfs)

http://poj.org/problem?id=3126

题意是说,给定两个四位素数a b 问从a变换到b,最少需要变换几次. 变换的要求是,每次只能改变一个数字,而且中间过程得到的四位数也必须为素数. 因为提到最少变换几次,容易想到bfs,bfs第一次搜到的一定是最短步数.

先打个素数表 然后写个函数判断两个四位数有几位数字不同,如果只有一位,返回true,否则返回false 然后竟然wa了两次! 下表写错! pri[k++]=i;是先给pri[k]赋值,再k++; pri[++k]=i;才是先增加,再赋值.这个搞错了.所以wa了....sad

  1    
  2    /*************************************************************************
  3        > File Name: code/poj/3126.cpp
  4        > Author: 111qqz
  5        > Email: rkz2013@126.com 
  6        > Created Time: Fri 24 Jul 2015 01:16:23 AM CST
  7     ************************************************************************/
  8    
  9    #include<iostream>
 10    #include<iomanip>
 11    #include<cstdio>
 12    #include<algorithm>
 13    #include<cmath>
 14    #include<cstring>
 15    #include<string>
 16    #include<map>
 17    #include<set>
 18    #include<queue>
 19    #include<vector>
 20    #include<stack>
 21    #define y0 abc111qqz
 22    #define y1 hust111qqz
 23    #define yn hez111qqz
 24    #define j1 cute111qqz
 25    #define tm crazy111qqz
 26    #define lr dying111qqz
 27    using namespace std;
 28    #define REP(i, n) for (int i=0;i<int(n);++i)  
 29    typedef long long LL;
 30    typedef unsigned long long ULL;
 31    const int N =1E4+5;
 32    int pri[N],which[N];
 33    int a,b,k;
 34    bool flag;
 35    int d[N];
 36    bool prime(int x)
 37    {
 38        for ( int i = 2 ; i*i<=x ;i++ )
 39        {
 40    	  if (x %i==0) return false;
 41        }
 42        return true;
 43    }
 44    
 45    bool ok (int x,int y)
 46    {
 47        if (d[y]!=-1) return false;
 48        int res = 0; //记录两个数不对应不相等的数字的个数
 49        int xx=x,yy=y;
 50        while (x&&y)
 51        {
 52    	  if (x!=y) res++;
 53    	  x = x/10;
 54    	  y = y/10;
 55        }
 56     //   if (res==1) cout<<"x:"<<xx<<" y:"<<yy<<endl;
 57        if (res==1) return true;
 58        return false;
 59    }
 60    void bfs()
 61    {
 62        queue<int>x;
 63        memset(d,-1,sizeof(d));
 64        x.push(a);
 65        d[a]=0;
 66        while (!x.empty())
 67        {
 68    	  int px = x.front();
 69    //	  cout<<"px:"<<px<<endl;
 70    	  x.pop();
 71    	  if (px==b) return;
 72    	  for ( int i = 0 ;  i< k ; i++ )
 73    	  {
 74    		if (ok(px,pri[i]))
 75    		{
 76    		    d[pri[i]]=d[px]+1;
 77    		    x.push(pri[i]);
 78    		}
 79    	  }
 80        }
 81    
 82    
 83    }
 84    int main()
 85    {
 86         k =0;
 87        for ( int i = 1000; i <=9999; i++ )
 88        {
 89    	  if (prime(i))
 90    	  {
 91    		pri[k++]=i;
 92    	  
 93    	  }
 94        }
 95        int T;
 96       // cout<<pri[0]<<endl;
 97       // cout<<pri[1]<<endl;
 98        cin>>T;
 99        while (T--)
100        {
101    	  cin>>a>>b;
102    	  bfs();
103    	  if (d[b]==-1)
104    	  {
105    		cout<<"Impossible"<<endl;
106    	  }
107    	  else
108    	  {
109    		cout<<d[b]<<endl;
110    	  }
111    
112        }
113    
114      
115    	return 0;
116    }
117