worm

为什么我的眼里饱含泪水?因为我程序没写完!
随笔 - 5, 文章 - 2, 评论 - 10, 引用 - 0
数据加载中……

poj 3126 Prim Path 第一道BFS

      对于一个四位数,对于它某一位变化之后的素数,即“相邻的素数”,进行广度搜索,知道搜索到为止!
挺简单,看代码应该可以看懂,下面是代码
9#include <iostream>
10#include <queue>
11#include <math.h>
12using namespace std;
13int a, b;
14int p[9999= 0 };
15int visited[9999= 0 };
16bool isprime(int x) {
17
18    for (int i = 2; i <= sqrt((double) x); ++i) {
19        if (x % i == 0)
20            return false;
21    }

22    return true;
23}

24int BFS(int s, int r) {
25    queue<int> q;
26    q.push(s);
27    p[s] = 0;
28    visited[s] = 1;
29    while (!q.empty()) {
30        int temp = q.front();
31        q.pop();
32        for (int i = 0; i <= 9; i++{
33            int y1 = (temp / 10* 10 + i;
34            if (isprime(y1) && !visited[y1]) {
35                q.push(y1);
36                p[y1] = p[temp] + 1;
37                visited[y1] = 1;
38            }

39            int y2 = temp % 10 + (temp / 100* 100 + i * 10;
40            if (isprime(y2) && !visited[y2]) {
41                q.push(y2);
42                p[y2] = p[temp] + 1;
43                visited[y2] = 1;
44            }

45            int y3 = temp % 100 + (temp / 1000* 1000 + 100 * i;
46            if (isprime(y3) && !visited[y3]) {
47                q.push(y3);
48                p[y3] = p[temp] + 1;
49                visited[y3] = 1;
50            }

51            if (i != 0{
52                int y4 = temp % 1000 + i * 1000;
53                if (isprime(y4) && !visited[y4]) {
54                    q.push(y4);
55                    p[y4] = p[temp] + 1;
56                    visited[y4] = 1;
57                }

58            }

59            if (visited[r])
60                return p[r];
61        }

62
63    }

64    return 0;
65}

66int main() {
67    int n;
68    cin >> n;
69    while (n--{
70        memset(visited,0,sizeof(visited));
71        memset(p,0,sizeof(p));
72        cin >> a >> b;
73        cout << BFS(a, b) << endl;
74
75    }

76    return 0;
77}

78

posted on 2009-03-08 10:36 WORM 阅读(1173) 评论(1)  编辑 收藏 引用

评论

# re: poj 3126 Prim Path 第一道BFS  回复  更多评论   

已阅 移除
2009-03-08 20:26 | cppexplore

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