misschuer
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2009年4月
>
日
一
二
三
四
五
六
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
1
2
3
4
5
6
7
8
9
公告
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
as(2)
(rss)
bfs(1)
(rss)
dfs
(rss)
dp(2)
(rss)
Java(2)
(rss)
mathematics(3)
(rss)
netty
(rss)
prim
(rss)
tt
(rss)
贪心
(rss)
字典数
(rss)
文章分类
acm
(rss)
Java
(rss)
随笔档案
2018年4月 (1)
2017年12月 (4)
2015年5月 (2)
2013年11月 (1)
2012年8月 (2)
2011年11月 (1)
2011年9月 (1)
2011年8月 (1)
2011年5月 (1)
2011年4月 (2)
2011年3月 (16)
2010年10月 (1)
2010年4月 (3)
2010年3月 (1)
2010年1月 (4)
2009年12月 (2)
2009年5月 (3)
2009年4月 (15)
文章档案
2009年4月 (1)
阅读排行榜
1. hdu 1402 A * B Problem Plus (1883)
2. alchemy c 图像的缩放 (三次卷积)(1736)
3. A*算法求第k短路(1050)
4. 合并果子 (907)
5. hdu 1421 搬寝室 详解(825)
评论排行榜
1. hdu 1402 A * B Problem Plus (6)
2. hdu 1175 连连看(4)
3. ZOJ 3194 Coverage (3)
4. hdu 1421 搬寝室 详解(3)
5. 竞赛图 (2)
常用链接
我的随笔
我的评论
我参与的随笔
统计
随笔 - 61
文章 - 1
评论 - 18
引用 - 0
积分与排名
积分 - 24158
排名 - 730
百事通
hao123
WPL
杭电
松松
星和
最新评论
1. re: 竞赛图
怎么感觉理论就有问题,太坑爹了
--此最相思
2. re: hdu 1175 连连看
由于HDU的数据不强所以 代码是有点错误
--misschuer
3. re: hdu 1175 连连看
@Xy
我表示刚看到 然后测试了一下 可以过的吧
--misschuer
4. re: hdu 1175 连连看
评论内容较长,点击标题查看
--ahfywff
5. re: hdu 1175 连连看[未登录]
你的代码WA的
--Xy
zoj 1002 Fire Net
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
1
#include
<
iostream
>
2
#include
<
queue
>
3
#define
M 6
4
using
namespace
std;
5
6
typedef
struct
point
{
7
int
i , j, cnt;
8
friend
bool
operator
<
(point a, point b)
{
9
return
a.cnt
<
b.cnt;
10
}
11
}
point;
12
13
priority_queue
<
point
>
Q;
14
char
str[ M ][ M ];
15
int
n , cnt;
16
17
void
endeavor (
int
x ,
int
y)
{
18
//
a point has four directions
19
//
for each piont we could divide into five Situations: None direct has wall , One
, Two
,Three
, Four
;
20
int
i , j;
21
cnt
=
0
;
22
for
(i
=
y
+
1
;i
<
n;
++
i)
{
23
if
(str[ x ][ i ]
==
'
X
'
)
{
24
cnt
++
;
break
;
25
}
26
}
27
28
for
(i
=
y
-
1
;i
>=
0
;
--
i)
{
29
if
(str[ x ][ i ]
==
'
X
'
)
{
30
cnt
++
;
break
;
31
}
32
}
33
34
for
(i
=
x
+
1
;i
<
n;
++
i)
{
35
if
(str[ i ][ y ]
==
'
X
'
)
{
36
cnt
++
;
break
;
37
}
38
}
39
40
for
(i
=
x
-
1
;i
>=
0
;
--
i)
{
41
if
(str[ i ][ y ]
==
'
X
'
)
{
42
cnt
++
;
break
;
43
}
44
}
45
46
}
47
48
void
init ()
{
49
point p;
50
for
(
int
i
=
0
;i
<
n;
++
i)
{
51
for
(
int
j
=
0
;j
<
n;
++
j)
{
52
if
(str[ i ][ j ]
==
'
.
'
)
{
53
p.i
=
i; p.j
=
j;
54
endeavor(i , j);
55
p.cnt
=
cnt;
56
Q.push(p);
57
}
58
}
59
}
60
}
61
62
void
recover (
int
x ,
int
y)
{
63
int
i , j;
64
for
(i
=
y
+
1
;i
<
n;
++
i)
{
65
if
(str[ x ][ i ]
==
'
X
'
)
break
;
66
str[ x ][ i ]
=
'
N
'
;
67
}
68
69
for
(i
=
y
-
1
;i
>=
0
;
--
i)
{
70
if
(str[ x ][ i ]
==
'
X
'
)
break
;
71
str[ x ][ i ]
=
'
N
'
;
72
}
73
74
for
(i
=
x
+
1
;i
<
n;
++
i)
{
75
if
(str[ i ][ y ]
==
'
X
'
)
break
;
76
str[ i ][ y ]
=
'
N
'
;
77
}
78
79
for
(i
=
x
-
1
;i
>=
0
;
--
i)
{
80
if
(str[ i ][ y ]
==
'
X
'
)
break
;
81
str[ i ][ y ]
=
'
N
'
;
82
}
83
}
84
85
void
GY ()
{
86
point p;
int
ans
=
0
;
87
while
(
!
Q.empty())
{
88
p
=
Q.top();
89
Q.pop();
90
if
(str[p.i][p.j]
==
'
.
'
)
{
91
ans
++
;
92
str[p.i][p.j]
=
'
O
'
;
93
recover (p.i , p.j);
94
}
95
else
continue
;
96
}
97
cout
<<
ans
<<
endl;
98
}
99
100
int
main()
{
101
while
(cin
>>
n
&&
n)
{
102
for
(
int
i
=
0
;i
<
n;
++
i)
{
103
cin
>>
str[ i ];
104
}
105
init ();
106
GY ();
107
}
108
return
0
;
109
}
还有一种可用图论做
网络流或者二分图的最大匹配
对于每行每列的连通块定义一个不同的编号,然后上面的算法选一个算
posted on 2010-04-24 13:03
此最相思
阅读(236)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理
Powered by:
C++博客
Copyright © 此最相思