欢迎您来到Tanky Woo的博客：
我们的【C++奋斗乐园】
C++/算法网站：www.cpply.com
C++/算法论坛：www.cppleyuan.com
QQ群：①群：19333724 ②群：23840480 ③群：17314377 ④群:23829384
谁说这道题简单？是水题？
又让我郁闷了。
思路：枚举，BFS,位操作
分析：要求输入一个4*4的棋盘，考虑状态是否全为黑或者全为白，状态共有2^16种，联系棋盘是4*4，可以想到用位来压缩状态。
bwwb
bbwb
bwwb
bwww
可以表示为：0001|1001|1011|1001
这里对位操作介绍下：
id ^= (1 << i) //对整数id转换成二进制后的第i位取反
其次，这里是广搜，用队列表示。
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 [...]
文章来源:
http://www.wutianqi.com/?p=280
posted on 2010-07-06 18:37
Tanky Woo 阅读(1118)
评论(0) 编辑 收藏 引用