worm
为什么我的眼里饱含泪水?因为我程序没写完!
随笔 - 5, 文章 - 2, 评论 - 10, 引用 - 0
数据加载中……
poj 3126 Prim Path 第一道BFS
对于一个四位数,对于它某一位变化之后的素数,即“相邻的素数”,进行广度搜索,知道搜索到为止!
挺简单,看代码应该可以看懂,下面是代码
9
#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
18
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
63
}
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
75
}
76
return
0
;
77
}
78
posted on 2009-03-08 10:36
WORM
阅读(1283)
评论(1)
编辑
收藏
引用
评论
#
re: poj 3126 Prim Path 第一道BFS
回复
更多评论
已阅 移除
2009-03-08 20:26 |
cppexplore
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © WORM
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2024年8月
>
日
一
二
三
四
五
六
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔档案
2009年3月 (5)
文章档案
2009年3月 (2)
相册
me
OJ
PKU
搜索
最新评论
1. re: 第一道广度搜索BFS纪念 poj 3278 源代码
你那段英语翻译过来:
但是关于我,我真的开心对它,我高潮了!蠕虫永远不放弃!
--english teacher
2. re: 第一道广度搜索BFS纪念 poj 3278 源代码
膜拜下··
--hm
3. re: 第一道广度搜索BFS纪念 poj 3278 源代码
评论内容较长,点击标题查看
--hj
4. re: poj 3414解题报告(广搜题)
那我写啥?@A
--WORM
5. re: poj 3126 Prim Path 第一道BFS
已阅 移除
--cppexplore
阅读排行榜
1. poj 3414解题报告(广搜题)(1638)
2. poj 3126 Prim Path 第一道BFS(1283)
3. 第一道广度搜索BFS纪念 poj 3278 源代码(1283)
4. poj 3191解题报告(1143)
5. poj 3705解题思路及源代码(303)
评论排行榜
1. poj 3414解题报告(广搜题)(5)
2. 第一道广度搜索BFS纪念 poj 3278 源代码(3)
3. poj 3191解题报告(1)
4. poj 3126 Prim Path 第一道BFS(1)
5. poj 3705解题思路及源代码(0)