問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1753思路:
首先，觀察題意，可以發(fā)現(xiàn)對于每個piece，最多只有兩種可能性: 翻轉(zhuǎn)一次或者不翻轉(zhuǎn)，翻轉(zhuǎn)多次是沒有意義的
另外，由于整個rectangular大小是4X4，因此可以使用位運算來提高性能
對于位運算，需要知道的是如何反轉(zhuǎn)任意的某一位:
巧妙的異或運算 1^x = ~x 0^x = x
1. 深度優(yōu)先搜索
1 #define SIZE 4
2 #define BIT_MAX 16
3 const int END_BLACK = 0;
4 const int END_WHITE = (1<<(BIT_MAX))-1;
5 int min;
6
7 int
8 flip(int init_state, int bit_num)
9 {
10 int x, y;
11 x = bit_num / SIZE;
12 y = bit_num % SIZE;
13 init_state ^= (1<<bit_num);
14 if(x == 0)
15 init_state ^= (1<<(bit_num+SIZE));
16 else if(x == 3)
17 init_state ^= (1<<(bit_num-SIZE));
18 else {
19 init_state ^= (1<<(bit_num+SIZE));
20 init_state ^= (1<<(bit_num-SIZE));
21 }
22 if(y==0)
23 init_state ^= (1<<(bit_num+1));
24 else if(y==3)
25 init_state ^= (1<<(bit_num-1));
26 else {
27 init_state ^= (1<<(bit_num+1));
28 init_state ^= (1<<(bit_num-1));
29 }
30 return init_state;
31 }
32
33 void
34 dfs(long state, int depth, int count)
35 {
36 if(state==END_BLACK || state==END_WHITE) {
37 min = count < min ? count : min;
38 return;
39 }
40 if(depth >= BIT_MAX || count >= min)
41 return;
42 dfs(state, depth+1, count);
43 dfs(flip(state, depth), depth+1, count+1);
44 }
2. 寬度優(yōu)先搜索
1 #define SIZE 4
2 #define BIT_MAX 16
3 const int END_BLACK = 0;
4 const int END_WHITE = (1<<(BIT_MAX))-1;
5 /* up, down, left, right */
6 const int dx[] = {-1, 1, 0, 0};
7 const int dy[] = {0, 0, -1, 1};
8 const int idx_diff[] = {-SIZE, SIZE, -1, 1};
9 struct State {
10 long state;
11 int count; /* minimum number of rounds needed to reach 'state' */
12 };
13 struct State queue[1<<BIT_MAX];
14 int visited[1<<BIT_MAX];
15 int head, tail;
16 long state; /* the low 16 bits represents the current state */
17
18 int
19 is_valid(int x, int y)
20 {
21 return (x>=0 && x<SIZE && y>=0 && y<SIZE);
22 }
23
24 /*
25 * tricky of bit-operation
26 * 1 ^ x = ~x
27 * 0 ^ x = x
28 */
29 long
30 flip(long state, int x, int y)
31 {
32 int i, index = x*SIZE + y;
33 state ^= (1<<index);
34 for(i=0; i<4; i++) {
35 if(is_valid(x+dx[i], y+dy[i]))
36 state ^= (1<<(index+idx_diff[i]));
37 }
38 return state;
39 }