• <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

            代碼完全可以優化,比如定義一個結構體可以省掉result數組!
            懶得改了
            發現poj比joj更驚心動魄?。〗洺ompling,結果半天才出現!
            posted on 2009-05-13 23:32 luis 閱讀(707) 評論(2)  編輯 收藏 引用 所屬分類: 搜索

            FeedBack:
            # re: poj 3126 廣搜
            2009-06-29 15:18 | 等等等
            為什么BFS中定義的k明明沒有用,刪除后答案卻不對了呢!??!
            不懂啊!!!  回復  更多評論
              
            # 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;//這個k沒用,我刪除后提交還是AC了
            int num[3];
            -----------  回復  更多評論
              
            <2011年2月>
            303112345
            6789101112
            13141516171819
            20212223242526
            272812345
            6789101112

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久亚洲欧洲日产国码是AV| 久久九九久精品国产免费直播| 伊人久久大香线蕉精品不卡| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 久久线看观看精品香蕉国产| 国产69精品久久久久9999| 久久久久综合中文字幕| 色综合久久无码中文字幕| 久久久久久综合一区中文字幕| 久久久久人妻一区精品果冻| 无码人妻久久一区二区三区免费丨| 天天爽天天爽天天片a久久网| 热综合一本伊人久久精品| 热RE99久久精品国产66热| 久久AV高清无码| 色老头网站久久网| 欧美亚洲另类久久综合| 久久久久久久精品成人热色戒| 亚洲精品高清久久| 久久综合88熟人妻| 久久香综合精品久久伊人| 国产 亚洲 欧美 另类 久久| 国产精品久久久久国产A级| 欧美亚洲国产精品久久高清| 久久99精品久久久久久齐齐| 国产精品久久一区二区三区| 国产美女亚洲精品久久久综合| 久久久久久久久久久免费精品| 欧美亚洲国产精品久久蜜芽| 天堂久久天堂AV色综合 | 日本WV一本一道久久香蕉| 亚洲国产精品久久久久久| av无码久久久久不卡免费网站| 精品久久久久久久国产潘金莲| 久久强奷乱码老熟女网站| 国产精品欧美久久久久无广告| 丰满少妇人妻久久久久久| 国产99精品久久| 色成年激情久久综合| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 精品国产日韩久久亚洲|