HooLee
If you believe, you can!
C++博客
首页
新随笔
新文章
联系
管理
poj1021_2D-Nim
题意：对比连个图是否相同。相同的条件是A图中每个连通的区域都在B图中有一块相同的区域与之对应。经过旋转后对应也可以。
解题思路：
思路一：暴力式。遍历并存储A图中所有联通的区域，然后在B中逐个寻找与之对应的图形。
思路二：等价转化式。比较两个图中对应点的“连通度”是否相同。相同输出YES。空白点的连通度为0，空白点的连通度为它所在行和列与之相连的非空白点的个数。
方式二非常巧妙，将二维问题转化为了一维问题，大大简化了问题。
代码
1
import
java.io.
*
;
2
import
java.util.
*
;
3
class
Main
4
{
5
private
static
int
[][] map1
=
new
int
[
110
][
110
];
6
private
static
int
[][] map2
=
new
int
[
110
][
110
];
7
private
static
CountNode[] ctnd1
=
new
CountNode[
110
*
110
];
8
private
static
CountNode[] ctnd2
=
new
CountNode[
110
*
110
];
9
private
static
int
col;
10
private
static
int
row;
11
public
static
void
main(String[] args)
12
{
13
14
Scanner sc
=
new
Scanner(System.in);
15
int
t
=
sc.nextInt();
16
for
(
int
ii
=
0
; ii
<
t; ii
++
)
17
{
18
for
(
int
j
=
0
; j
<
map1.length; j
++
)
19
{
20
Arrays.fill(map1[j],
0
);
21
Arrays.fill(map2[j],
0
);
22
}
23
Arrays.fill(ctnd1,
new
CountNode(
0
));
24
Arrays.fill(ctnd2,
new
CountNode(
0
));
25
26
col
=
sc.nextInt();
27
row
=
sc.nextInt();
28
int
n
=
sc.nextInt();
29
int
thiscol, thisrow;
30
//
31
//
System.out.println("col=" + col + " row=" + row + " n=" + n);
32
//
33
for
(
int
k
=
0
; k
<
n; k
++
)
//
read map1[][]
34
{
35
thiscol
=
sc.nextInt();
36
thisrow
=
sc.nextInt();
37
38
map1[thisrow][thiscol]
=
1
;
39
}
40
for
(
int
k
=
0
; k
<
n; k
++
)
//
read map2[][]
41
{
42
thiscol
=
sc.nextInt();
43
thisrow
=
sc.nextInt();
44
45
map2[thisrow][thiscol]
=
1
;
46
}
47
//
48
/**/
/*
System.out.println("map1[][]");
49
for(int i = 0; i < row; i++)
50
{
51
for(int j = 0; j < col; j++)
52
System.out.print(map1[i][j]);
53
System.out.println();
54
}
55
System.out.println("map2[][]");
56
for(int i = 0; i < row; i++)
57
{
58
for(int j = 0; j < col; j++)
59
System.out.print(map2[i][j]);
60
System.out.println();
61
}
*/
62
//
63
getAllCounts();
64
Arrays.sort(ctnd1);
65
Arrays.sort(ctnd2);
66
boolean
flag
=
true
;
67
for
(
int
i
=
0
; i
<
ctnd1.length; i
++
)
68
{
69
if
(ctnd1[i].getCount()
!=
ctnd2[i].getCount())
{
70
flag
=
false
;
71
System.out.println(
"
NO
"
);
72
break
;
73
}
74
}
75
if
(flag)
76
System.out.println(
"
YES
"
);
77
}
78
79
}
80
private
static
void
getAllCounts()
81
{
82
int
p
=
0
;
83
for
(
int
i
=
0
; i
<
row; i
++
)
84
{
85
for
(
int
j
=
0
; j
<
col; j
++
)
86
{
87
if
(map1[i][j]
==
1
)
88
ctnd1[p
++
]
=
new
CountNode(getThisMap1Counts(i, j));
89
if
(map2[i][j]
==
1
)
90
ctnd2[p
++
]
=
new
CountNode(getThisMap2Counts(i, j));
91
}
92
}
93
}
94
private
static
int
getThisMap1Counts(
int
r,
int
c)
//
map1[][]的连通度
95
{
96
int
count
=
0
;
97
for
(
int
i
=
r
-
1
; i
>=
0
&&
map1[i][c]
==
1
; i
--
)
98
count
++
;
99
for
(
int
i
=
r
+
1
; i
<
row
&&
map1[i][c]
==
1
; i
++
)
100
count
++
;
101
for
(
int
i
=
c
-
1
; i
>=
0
&&
map1[r][i]
==
1
; i
--
)
102
count
++
;
103
for
(
int
i
=
c
+
1
; i
<
col
&&
map1[r][i]
==
1
; i
++
)
104
count
++
;
105
return
count
+
1
;
106
}
107
private
static
int
getThisMap2Counts(
int
r,
int
c)
//
map2[][]的连通度
108
{
109
int
count
=
0
;
110
for
(
int
i
=
r
-
1
; i
>=
0
&&
map2[i][c]
==
1
; i
--
)
111
count
++
;
112
for
(
int
i
=
r
+
1
; i
<
row
&&
map2[i][c]
==
1
; i
++
)
113
count
++
;
114
for
(
int
i
=
c
-
1
; i
>=
0
&&
map2[r][i]
==
1
; i
--
)
115
count
++
;
116
for
(
int
i
=
c
+
1
; i
<
col
&&
map2[r][i]
==
1
; i
++
)
117
count
++
;
118
return
count
+
1
;
119
}
120
121
122
}
123
class
CountNode
implements
Comparable
<
CountNode
>
124
{
125
private
int
count;
126
public
CountNode(
int
count)
127
{
128
this
.count
=
count;
129
}
130
public
int
getCount()
131
{
132
return
count;
133
}
134
public
int
compareTo(CountNode n2)
135
{
136
return
n2.count
-
this
.count;
137
}
138
}
139
posted on 2013-04-14 20:10
小鼠标
阅读(499)
评论(0)
编辑
收藏
引用
所属分类:
Java基础练习
只有注册用户
登录
后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！
相关文章:
编辑距离
闰年判断
正则表达式简单笔记
Excel格式地址转换
一道模拟题——机器人行走距离计算
排列练习2
素数筛法
排列组合练习
排列组合
poj1068Parencodings
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2012年8月
>
日
一
二
三
四
五
六
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
8
常用链接
我的随笔
我的评论
我参与的随笔
随笔分类
(111)
C语言(3)
DP(9)
Java笔记(1)
Java基础练习(25)
安卓(1)
本科毕设(1)
博弈(1)
大数(7)
回溯(2)
排序(10)
暑期培训周赛(3)
数据结构(7)
数论(1)
水题(8)
图论(24)
网选训练(8)
随笔档案
(127)
2014年3月 (1)
2013年7月 (10)
2013年5月 (1)
2013年4月 (11)
2013年3月 (8)
2012年10月 (1)
2012年9月 (12)
2012年8月 (38)
2012年7月 (14)
2012年6月 (2)
2012年5月 (8)
2012年4月 (6)
2012年3月 (6)
2012年2月 (4)
2011年8月 (5)
friends
陈钢
大鹏
党姐
焦林枫
汪涛
小白学长
媛姐
媛姐csdn
最新评论
1. re: 线段树
是这个样子的，所以在OJ有时候“卡住”了也不要太灰心，没准真的不是自己的原因呢。
加油，祝你好运啦！
--小鼠标
2. re: 线段树
对于编程竞赛来说，Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
--伤心的笔
3. re: poj1273--网络流
过来看看你。
--achiberx
4. re: （转）ubuntu11.10无法启动无线网络的解决方法
膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。？
--Hang
5. re: 快速排序、线性时间选择
博主，谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况，书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
--lsxqw2004
阅读排行榜
1. 单调队列(5480)
2. Linux select()函数使用(3954)
3. 快速排序、线性时间选择(3619)
4. poj3468--绝对经典的线段树题(3610)
5. 优先队列--堆实现(3291)