歡迎您來(lái)到Tanky Woo的博客：
我們的【C++奮斗樂(lè)園】
C++/算法網(wǎng)站：www.cpply.com
C++/算法論壇：www.cppleyuan.com
QQ群：①群：19333724 ②群：23840480 ③群：17314377 ④群:23829384
?誰(shuí)說(shuō)這道題簡(jiǎn)單？是水題？
又讓我郁悶了。
思路：枚舉，BFS,位操作
分析：要求輸入一個(gè)4*4的棋盤，考慮狀態(tài)是否全為黑或者全為白，狀態(tài)共有2^16種，聯(lián)系棋盤是4*4，可以想到用位來(lái)壓縮狀態(tài)。
bwwb
bbwb
bwwb
bwww
可以表示為：0001|1001|1011|1001
這里對(duì)位操作介紹下：
id ^= (1 << i)?? //對(duì)整數(shù)id轉(zhuǎn)換成二進(jìn)制后的第i位取反
其次，這里是廣搜，用隊(duì)列表示。
queue的front(), pop(), push()要掌握。
題目地址：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1753
?Memory:?504K
?
?
?Time:?16MS
?
?Language:?C++
?
?
?Result:?Accepted
自定義難度：★★★☆☆
代碼：
?
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// POJ 1753
// Author: Tanky Woo
#include <iostream>
#include <queue>
using namespace std;
const int MAX_STATE = 65536;
const int ALL_BLACK = 65535;
const int ALL_WHITE = 0;
const int SIZE = 4;
// www.wutianqi.com
int convert(char c)
{
if(c == 'b')
return 1;
else
return 0;
}
int FlipPiece(int state_id, int pos)
{
state_id ^= (1 << pos);
//up
if(pos >= 4)
state_id [...]
文章來(lái)源:
http://www.wutianqi.com/?p=280
posted on 2010-07-06 18:37
Tanky Woo 閱讀(1125)
評(píng)論(0) 編輯 收藏 引用