worm

為什么我的眼里飽含淚水？因?yàn)槲页绦驔](méi)寫(xiě)完！

隨筆 - 5, 文章 - 2, 評(píng)論 - 10, 引用 - 0

數(shù)據(jù)加載中……

poj 3126 Prim Path 第一道BFS

對(duì)于一個(gè)四位數(shù)，對(duì)于它某一位變化之后的素?cái)?shù)，即“相鄰的素?cái)?shù)”，進(jìn)行廣度搜索，知道搜索到為止！
挺簡(jiǎn)單，看代碼應(yīng)該可以看懂，下面是代碼

#include <iostream>
10

#include <queue>
11

#include <math.h>
12

using namespace std;
13

int a, b;
14

int p[9999] = { 0 };
15

int visited[9999] = { 0 };
16

bool isprime(int x) {
17

for (int i = 2; i <= sqrt((double) x); ++i) {
19

if (x % i == 0)
20

return false;
21

}
22

return true;
23

}
24

int 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

}
64

return 0;
65

}
66

int 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

}
76

return 0;
77

}
78

posted on 2009-03-08 10:36 WORM 閱讀(1346) 評(píng)論(1) 編輯收藏引用

評(píng)論

# re: poj 3126 Prim Path 第一道BFS 回復(fù) 更多評(píng)論

已閱移除

2009-03-08 20:26 | cppexplore

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

# re: poj 3126 Prim Path 第一道BFS 回復(fù) 更多評(píng)論

worm

poj 3126 Prim Path 第一道BFS

評(píng)論

導(dǎo)航

常用鏈接

留言簿(1)

隨筆檔案

文章檔案

相冊(cè)

OJ

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜