首页 > 代码库 > PRIME PATH

PRIME PATH

2024-07-28 20:10:19   215人阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1450
输入：
     两个素数s和e（1000<s,e<9999）
输出：
    每次改变一位（要求生成的数也为素数且最高位非0），输出s到e的改变的最小次数。
解题思路：
      1.经典的bfs，当某一个节点的值第一次等于e的时候即为所求，且一定改变次数最小。
       2.用两个队列，队列1存解空间树的奇数层节点，队列2存解空间树的偶数层节点。
      3.两个队列循环出队列，入队列，队列1出的时候生成的节点全部入队列2，队列2出的时候生成的节点全部入队列1。当队列1或队列2空的时候步数加1。

核心代码：

?
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
        q1.push(s);
        isvis[s]=true;
        while(!q1.empty())
        {
            while(!q1.empty())
            {
                tmp=q1.front();
                q1.pop();
                if(tmp==e)
                {
                    flag=true;
                    break;
                }
                for(j=0;j<4;j++)
                {
                    dat[j]=tmp%10;
                    tmp/=10;
                }
                for(j=0;j<4;j++)
                {
                    tmp=0;
                    for(k=0;k<4;k++)
                        if(k!=j)
                            tmp+=dat[k]*pow((double)10,(double)k);
                    for(k=0;k<=9;k++)
                    {
                        tmp+=k*pow((double)10,(double)j);
                        if(v[tmp]==false&&tmp>1000&&isvis[tmp]==false)
                        {
                            q2.push(tmp);
                            isvis[tmp]=true;
                        }
                        tmp-=k*pow((double)10,(double)j);
                    }
                }
            }
            if(flag==true)
                break;
            cnt++;
            while(!q2.empty())
            {
                tmp=q2.front();
                q2.pop();
                q1.push(tmp);
            }
              
        }

PRIME PATH


联系
我们