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 阅读(1310) 评论(1)  编辑 收藏 引用

评论

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

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理