• <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 - 195,  comments - 30,  trackbacks - 0
            #include<iostream>
            #include
            <queue>
            #include
            <math.h>
            using namespace std;
            const int MAX=10000;
            int visited[10000];
            int result[10000];
            bool isprimer(int npp)
             {
                 
            for (int q = 2; q <= sqrt(double(npp)); ++q)
                 {
                     
            if (npp % q == 0)
                     {
                         
            return 0;
                     }
                 }
                 
            return 1;
             
             }

            int BFS(int start,int end) 
            {
                queue
            <int> q;
                
            if (start == end)
                    
            return 0;
                q.push(start);
                visited[start]
            =1;
                result[start]
            =0;
                
            while(!q.empty()) 
                {
                    
            int temp=q.front();
                    q.pop();
                    
            int next,j,k;
                    
            int num[3];
                    
                    
            for (int i =0;i<4;++i)
                        {    
                             num[
            0]=temp%10;
                             num[
            1]=(temp%100)/10;
                             num[
            2]=(temp%1000)/100;
                             num[
            3]=temp/1000;   
                             
            for(j=0;j<=9;j++)      
                           {                       
                             num[i]
            =j;
                             next
            =num[0]+num[1]*10+num[2]*100+num[3]*1000;
                             
                             
            if((next>1000&&visited[next]!=1)&&isprimer(next))
                             {
                                 q.push(next);
                                 result[next]
            =result[temp]+1;
                                 visited[next]
            =1;                                             
                             }
                             
            if(next==end)
                             {
                               
            return result[next];           
                             }
                          }     
                        } 
                }
                
            return MAX;
            }
            int main() {
                
            //freopen("s.txt","r",stdin);
                
            //freopen("key.txt","w",stdout);
                int n,k,j,m;
                cin
            >>j;
                
            while(j--)
                {
                memset(visited,
            0,sizeof(visited));
                memset(result,
            0,sizeof(result));          
                cin
            >>n>>k;
                m
            =BFS(n,k);
                
            if(m!=MAX)          
                cout
            <<m<<endl;
                
            else
                cout
            <<"Impossible"<<endl;
                }
                
            return 0;
            }

            Description

            The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
            — It is a matter of security to change such things every now and then, to keep the enemy in the dark.
            — But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
            — I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
            — No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
            — I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
            — Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

            Now, the minister of finance, who had been eavesdropping, intervened.
            — No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
            — Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
            — In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
            1033
            1733
            3733
            3739
            3779
            8779
            8179
            The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

            Input

            One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

            Output

            One line for each case, either with a number stating the minimal cost or containing the word Impossible.

            Sample Input

            3
            1033 8179
            1373 8017
            1033 1033

            Sample Output

            6
            7
            0

            代碼完全可以?xún)?yōu)化,比如定義一個(gè)結(jié)構(gòu)體可以省掉result數(shù)組!
            懶得改了
            發(fā)現(xiàn)poj比joj更驚心動(dòng)魄啊!經(jīng)常compling,結(jié)果半天才出現(xiàn)!
            posted on 2009-05-13 23:32 luis 閱讀(710) 評(píng)論(2)  編輯 收藏 引用 所屬分類(lèi): 搜索

            FeedBack:
            # re: poj 3126 廣搜
            2009-06-29 15:18 | 等等等
            為什么BFS中定義的k明明沒(méi)有用,刪除后答案卻不對(duì)了呢?。?!
            不懂?。。。?nbsp; 回復(fù)  更多評(píng)論
              
            # re: poj 3126 廣搜
            2009-06-30 10:59 | luis
            @等等等
            m=BFS(n,k);中的k是有用的,
            -----
            while(!q.empty())
            {
            int temp=q.front();
            q.pop();
            int next,j,k;//這個(gè)k沒(méi)用,我刪除后提交還是AC了
            int num[3];
            -----------  回復(fù)  更多評(píng)論
              
            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            常用鏈接

            留言簿(3)

            隨筆分類(lèi)

            隨筆檔案

            文章分類(lèi)

            文章檔案

            友情鏈接

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            亚洲精品乱码久久久久久久久久久久| 97久久天天综合色天天综合色hd| 91精品国产91热久久久久福利| 一本伊大人香蕉久久网手机| 一级做a爰片久久毛片人呢| 久久天天躁狠狠躁夜夜av浪潮| 久久天天躁狠狠躁夜夜2020一| 久久66热人妻偷产精品9| 国产成人综合久久精品尤物| 久久经典免费视频| 久久青草国产手机看片福利盒子| 久久亚洲AV永久无码精品| 久久人妻无码中文字幕| 国产激情久久久久影院老熟女| 久久久SS麻豆欧美国产日韩| 久久香蕉国产线看观看乱码| 久久这里有精品| 亚洲乱亚洲乱淫久久| 欧美熟妇另类久久久久久不卡 | 久久久久久国产精品美女| 久久精品国产亚洲av瑜伽| 亚洲国产精品无码久久久不卡| 久久精品无码av| 久久婷婷国产麻豆91天堂| 7777精品久久久大香线蕉 | 国产精品久久久久久| 伊人久久精品影院| 久久久久国产精品三级网| 777米奇久久最新地址| 伊人久久大香线蕉av不卡| 性做久久久久久久久久久| 久久国产影院| 精品免费久久久久国产一区| 一本大道加勒比久久综合| 精品综合久久久久久97超人| 久久精品中文字幕无码绿巨人| 精品一二三区久久aaa片| 久久久久免费精品国产| 亚洲精品无码久久毛片| 色99久久久久高潮综合影院| 四虎影视久久久免费观看|