• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 100,  comments - 15,  trackbacks - 0
            篩個素數表+BFS
            貌似數據里沒有impossible的情況
            #include<iostream>
            using namespace std;
            #define M 10000
            bool prime[M];
            bool visit[M];
            int s,e;
            int step;
            void crearprimetable()//篩素數表
            {
                   
            int i,j;
                   
            //prime[0]=prime[1]=1;
                   for(i=2;i<M;i++)      //判斷i是不是素數
                       if(prime[i]==0)        //
                           for(j=i+i;j<M;j+=i) //把是i倍數的數j記上1,不是素數.
                               prime[j]=1;

            }


            void bfs()
            {
                
            int i,j,k,num,t;
                
            int que[10000];
                
            int front,rear,trear;
                step
            =0;
                
            if(s==e) return ;
                front
            =rear=0;
                que[rear
            ++]=s;
                
            while(front<rear)
                
            {
                    step
            ++;
                    trear
            =rear;
                    
            while(front<trear)
                    
            {
                        num
            =que[front++];
                        
            for(i=1;i<10;i++)//換個位
                        {
                            t
            =num/10*10+i;
                            
            if(!prime[t] && !visit[t])
                                
            if(t==e) return ;
                                
            else  {que[rear++]=t;visit[t]=true;}
                        }

                        
            for(i=0;i<10;i++)//換十位
                        {
                            t
            =num/100*100+i*10+num%10;
                            
            if(!prime[t] && !visit[t])
                                
            if(t==e) return ;
                                
            else  {que[rear++]=t;visit[t]=true;}
                        }

                        
            for(i=0;i<10;i++)//換百位
                        {
                            t
            =num/1000*1000+i*100+num%100;
                            
            if(!prime[t] && !visit[t])
                                
            if(t==e) return ;
                                
            else  {que[rear++]=t;visit[t]=true;}
                        }

                        
            for(i=1;i<10;i++)//換百位
                        {
                            t
            =i*1000+num%1000;
                            
            if(!prime[t] && !visit[t])
                                
            if(t==e) return ;
                                
            else  {que[rear++]=t;visit[t]=true;}
                        }

                    }

                }


            }

            int main()
            {
                
            int n;
                crearprimetable();
                scanf(
            "%d",&n);
                
            while(n--)
                
            {
                    scanf(
            "%d%d",&s,&e);
                    memset(visit,
            0,sizeof(visit));
                    bfs();
                    printf(
            "%d\n",step);
                }

                
            return 0;
            }
            posted on 2009-07-23 16:27 wyiu 閱讀(180) 評論(0)  編輯 收藏 引用 所屬分類: POJ
            91久久香蕉国产熟女线看| 久久天堂AV综合合色蜜桃网| 日韩精品国产自在久久现线拍| 蜜桃麻豆www久久| 开心久久婷婷综合中文字幕| 思思久久精品在热线热| 97久久精品无码一区二区| 久久国产V一级毛多内射| 久久这里都是精品| 久久国产高清字幕中文| 国内精品人妻无码久久久影院导航 | 国产成人精品久久二区二区| 国产精品99久久久久久宅男| 久久91精品国产91| 国产精品成人99久久久久| 色8久久人人97超碰香蕉987| 久久久久无码中| 99久久精品影院老鸭窝| 性高朝久久久久久久久久| 久久免费小视频| 大伊人青草狠狠久久| 久久久久久久女国产乱让韩| 久久996热精品xxxx| 久久91精品久久91综合| 婷婷久久久亚洲欧洲日产国码AV| 狠狠色丁香婷婷综合久久来来去| 久久精品国产99久久无毒不卡 | 嫩草伊人久久精品少妇AV| 亚洲精品久久久www| 国内精品欧美久久精品| 久久99热国产这有精品| 国产亚洲精品自在久久| 亚洲av成人无码久久精品| 一个色综合久久| 久久露脸国产精品| 天天综合久久一二三区| 久久激情亚洲精品无码?V| 91久久九九无码成人网站| 97超级碰碰碰碰久久久久| 亚洲综合精品香蕉久久网97 | 狠狠色狠狠色综合久久|