青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
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
小鼠標
閱讀(517)
評論(0)
編輯
收藏
引用
所屬分類:
Java基礎練習
只有注冊用戶
登錄
后才能發表評論。
【推薦】100%開源!大型工業跨平臺軟件C++源碼提供,建模,組態!
相關文章:
編輯距離
閏年判斷
正則表達式簡單筆記
Excel格式地址轉換
一道模擬題——機器人行走距離計算
排列練習2
素數篩法
排列組合練習
排列組合
poj1068Parencodings
網站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
Copyright ©2025 小鼠標 Powered by:
博客園
模板提供:
滬江博客
<
2013年4月
>
日
一
二
三
四
五
六
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
10
11
常用鏈接
我的隨筆
我的評論
我參與的隨筆
隨筆分類
(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.?單調隊列(5507)
2.?Linux select()函數使用(4003)
3.?快速排序、線性時間選擇(3744)
4.?poj3468--絕對經典的線段樹題(3661)
5.?優先隊列--堆實現(3319)
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
一区二区欧美亚洲
|
亚洲精品综合在线
|
免费久久久一本精品久久区
|
亚洲国产婷婷
|
亚洲美女黄网
|
久久久亚洲高清
|
亚洲国产欧美国产综合一区
|
在线观看欧美亚洲
|
欧美视频网址
|
欧美高清视频在线
|
欧美精品日韩www.p站
|
久久手机免费观看
|
欧美日韩精品一区二区
|
一本色道久久88精品综合
|
欧美高清在线精品一区
|
久久免费黄色
|
久久精品国产清高在天天线
|
亚洲视频精选在线
|
亚洲午夜一区
|
亚洲欧美精品伊人久久
|
久久国产精品99久久久久久老狼
|
久久手机免费观看
|
午夜国产精品影院在线观看
|
嫩草国产精品入口
|
亚洲国产网站
|
亚洲国产视频一区
|
国产精品福利在线观看
|
亚洲欧美成人综合
|
亚洲欧美日韩精品一区二区
|
国产亚洲成精品久久
|
国产综合在线看
|
…久久精品99久久香蕉国产
|
国产精品亚洲激情
|
国产日韩久久
|
亚洲人线精品午夜
|
亚洲视频你懂的
|
欧美在线视频不卡
|
欧美高清不卡
|
欧美一区二区精品
|
国产精品自在在线
|
欧美一区二区成人
|
亚洲午夜精品福利
|
欧美日本韩国在线
|
亚洲综合视频一区
|
午夜在线一区
|
亚洲国产高清在线观看视频
|
亚洲国产裸拍裸体视频在线观看乱了
|
亚洲作爱视频
|
正在播放欧美一区
|
亚洲精品在线二区
|
欧美日韩精品欧美日韩精品一
|
亚洲人永久免费
|
99国产精品久久久久久久久久
|
国内久久视频
|
亚洲国产精品精华液网站
|
欧美日韩另类国产亚洲欧美一级
|
中文久久乱码一区二区
|
久久精品一本
|
亚洲欧美综合精品久久成人
|
久久久999成人
|
午夜久久久久久
|
欧美电影专区
|
欧美成人a视频
|
国产专区欧美精品
|
亚洲午夜国产成人av电影男同
|
尤物精品在线
|
久久久精品午夜少妇
|
久久精品91久久香蕉加勒比
|
欧美日韩伦理在线免费
|
欧美成人日本
|
亚洲国产精品尤物yw在线观看
|
午夜日韩在线观看
|
午夜欧美不卡精品aaaaa
|
欧美日韩一区二区在线视频
|
亚洲欧洲日韩综合二区
|
av成人毛片
|
国产精品白丝jk黑袜喷水
|
亚洲乱码国产乱码精品精可以看
|
久久精品国产一区二区电影
|
欧美日韩a区
|
宅男噜噜噜66一区二区
|
亚洲少妇中出一区
|
国产精品一区二区久久久久
|
欧美在线观看视频一区二区三区
|
午夜精品999
|
国产一区二区成人
|
欧美mv日韩mv国产网站app
|
亚洲国产精品久久久久秋霞不卡
|
亚洲成人资源
|
欧美日韩在线视频一区二区
|
亚洲欧美一区二区三区在线
|
久久精品盗摄
|
宅男精品视频
|
国内精品久久久久久影视8
|
久久伊人免费视频
|
一区二区三区精品
|
国产在线精品自拍
|
欧美四级在线
|
另类亚洲自拍
|
久久手机免费观看
|
亚洲制服欧美中文字幕中文字幕
|
久久久久久亚洲精品中文字幕
|
一区二区毛片
|
中国日韩欧美久久久久久久久
|
激情视频一区二区三区
|
国产精品久久久久9999
|
欧美精品国产精品日韩精品
|
久久不射电影网
|
亚洲欧美日韩综合
|
亚洲一区二区黄
|
一区二区91
|
欧美一区影院
|
久久国产一区
|
老**午夜毛片一区二区三区
|
亚洲欧美综合另类中字
|
亚洲免费视频网站
|
午夜精彩国产免费不卡不顿大片
|
亚洲成人在线视频播放
|
亚洲欧洲视频在线
|
亚洲毛片在线观看
|
在线一区二区日韩
|
先锋资源久久
|
久久久久久日产精品
|
女人天堂亚洲aⅴ在线观看
|
六月丁香综合
|
日韩网站在线看片你懂的
|
日韩午夜电影在线观看
|
欧美一级黄色录像
|
久久天堂av综合合色
|
欧美日韩一区二区在线观看视频
|
国产精品免费小视频
|
国内精品久久久久久久影视麻豆
|
久久成人亚洲
|
欧美激情欧美激情在线五月
|
国产精品老女人精品视频
|
韩国v欧美v日本v亚洲v
|
最新中文字幕一区二区三区
|
亚洲午夜久久久久久久久电影院
|
亚洲综合色激情五月
|
男人插女人欧美
|
国产精品久线观看视频
|
亚洲日韩视频
|
嫩草影视亚洲
|
久久久福利视频
|
黄色一区二区三区
|
欧美一区二区成人
|
一区二区三区高清在线
|
欧美岛国激情
|
亚洲区第一页
|
亚洲三级性片
|
欧美成人黄色小视频
|
久久精品国产一区二区三区
|
国产精品欧美日韩
|
亚洲一区中文
|
999亚洲国产精
|
国产精品ⅴa在线观看h
|
亚洲一区制服诱惑
|
亚洲午夜电影在线观看
|
国产精品日韩一区
|
久久亚洲春色中文字幕
|
欧美一级在线视频
|
在线观看亚洲视频
|
亚洲高清视频一区二区
|
欧美成人精品1314www
|
亚洲国产精品美女
|
亚洲国产精品专区久久
|
欧美三级不卡
|
久久久久一区二区三区
|
久久人人爽人人爽爽久久
|
亚洲免费观看在线观看
|
中日韩美女免费视频网址在线观看
|
国产精品剧情在线亚洲
|
老司机aⅴ在线精品导航
|
欧美精品福利在线
|
久久精品视频免费观看
|
亚洲小说欧美另类社区
|
久久激情婷婷
|
亚洲伊人网站
|
免费一区视频
|
老牛国产精品一区的观看方式
|
国产精品二区在线
|
亚洲日本va午夜在线影院
|
欧美午夜精彩
|
亚洲看片一区
|
亚洲乱码视频
|
欧美jizzhd精品欧美喷水
|
久久夜色精品
|
国产在线不卡精品
|
亚洲欧美www
|
欧美中文字幕久久
|
国产精品视频精品
|
亚洲特级毛片
|
久久高清免费观看
|
国产麻豆9l精品三级站
|
正在播放欧美视频
|
午夜免费久久久久
|
亚洲专区一二三
|
久久大逼视频
|
国产精品久久久一区二区三区
|
欧美大色视频
|