posts - 3,  comments - 1,  trackbacks - 0
第N道的广搜,这几天就准备做广搜了...真的需要好好练习下...



Prime Path
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 1877 Accepted: 1215

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
这题主要思路就是对每一位进行0-9的改变..第一位不能位0...得到的新数入队...循环直到找到Y


Source Code

Problem: 3126 User: luoguangyao
Memory: 344K Time: 47MS
Language: C++ Result: Accepted
  • Source Code
  •   1#include <iostream>
      2#include <math.h>
      3#include <queue>
      4#include <stdio.h>
      5
      6using namespace::std;
      7
      8int cnumber[10000];
      9
     10bool mark[10000];
     11
     12
     13bool isprimer(int npp)
     14{
     15    for (int q = 2; q <= sqrt(double(npp)); ++q)
     16    {
     17        if (npp % q == 0)
     18        {
     19            return 0;
     20        }

     21    }

     22    return 1;
     23
     24}

     25
     26
     27int main()
     28{
     29
     30//    freopen("1.txt","r",stdin);
     31
     32    int n;
     33    cin >> n;
     34
     35    while (n)
     36    {
     37        queue<int> number;
     38        int x;
     39        int y;
     40        int i;
     41        int j;
     42        int newnumber;
     43
     44        memset(cnumber,0,sizeof(cnumber));
     45        memset(mark,0,sizeof(mark));
     46        
     47        cin >> x >> y;
     48
     49
     50        cnumber[x] = 0;
     51
     52        number.push(x);
     53
     54        while (number.size())
     55        {
     56            newnumber = number.front();
     57
     58            int p = (newnumber % 1000/ 100;
     59
     60            int p1 = newnumber % 1000 % 100 / 10;
     61
     62            number.pop();
     63
     64            mark[newnumber] = 1;
     65    
     66            if (newnumber == y)
     67            {
     68                break;
     69            }

     70
     71            int num;
     72            
     73            for (i = 0; i <= 9++i)
     74            {
     75                num = newnumber % 1000 + i * 1000;
     76
     77                
     78                if (i != 0 && mark[num] != 1 && isprimer(num))
     79                {
     80                    number.push(num);
     81                    cnumber[num] = cnumber[newnumber] + 1;  
     82                    mark[num] = 1;
     83                }

     84        
     85                int num1;
     86                num1 = newnumber - p * 100 + i * 100;
     87
     88
     89                if (mark[num1] != 1 && isprimer(num1))
     90                {
     91
     92                    number.push(num1);
     93                    cnumber[num1] = cnumber[newnumber] + 1
     94                    mark[num1] = 1;
     95                }

     96                int num2;
     97                num2 = newnumber - p1 * 10 + i * 10;
     98
     99
    100                if (mark[num2] != 1 &&  isprimer(num2))
    101                {
    102                    number.push(num2);
    103                    cnumber[num2] = cnumber[newnumber] + 1
    104                    mark[num2] = 1;
    105                }

    106
    107                int num3 = newnumber / 10 * 10 + i;
    108    
    109                if (mark[num3] != 1 &&  isprimer(num3))
    110                {
    111                    number.push(num3);
    112                    cnumber[num3] = cnumber[newnumber] + 1
    113                    mark[num3] = 1;
    114                }

    115            }

    116            
    117        }

    118
    119        cout << cnumber[y] << endl;
    120
    121        n--;
    122    }

    123
    124    return 0;
    125}

    126
posted on 2009-03-08 11:23 生活要低调 阅读(1277) 评论(1)  编辑 收藏 引用

FeedBack:
# re: POJ 3126 学会广搜队列的用法
2009-03-08 20:25 | cppexplore
removed by cppexplore  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(1)

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜