欢迎您来到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 阅读(130)
评论(0) 编辑 收藏 引用