POJ 1753 Flip Game

 谁说这道题简单?是水题?

又让我郁闷了。

思路:枚举,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 ^= (1 << (pos-4));
	//down
	if(pos + 4 < SIZE*SIZE)
		state_id ^= (1 << (pos+4));
	//left
	if(pos % 4 != 0)
		state_id ^= (1<<(pos-1));
	//right
	if(pos % 4 != 3)
		state_id ^= (1 << (pos+1));
 
	return state_id;
}
 
int main()
{
	int current_state_id = 0;
	int state[MAX_STATE];
	queue<int> search_queue;
 
	memset(state, -1, sizeof(state));
 
	char color;
	for(int i = 0; i < SIZE*SIZE; i++)
	{
		cin >> color;
		current_state_id += convert(color) << i;
	}
 
	if(current_state_id == ALL_WHITE || current_state_id == ALL_BLACK)
	{
		printf("0\n");
		return 0;
	}
 
	state[current_state_id] = 0;
	search_queue.push(current_state_id);
 
	int next_state_id;
 
     while(!search_queue.empty())
	 {
		 current_state_id = search_queue.front();
         search_queue.pop();
 
         for(int i = 0; i < SIZE*SIZE; ++i)
		 {
			 next_state_id = FlipPiece(current_state_id, i);
             if(next_state_id == ALL_WHITE || next_state_id == ALL_BLACK)
             {
                 cout << state[current_state_id] + 1 << endl;
                 return 0;
             }
			 if(state[next_state_id] == -1 )   //not visit
			 {
				 state[next_state_id] = state[current_state_id] + 1;
				 search_queue.push(next_state_id);
			 }
		 }
	 }
	 cout << "Impossible" << endl;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《POJ 1753 Flip Game》有214个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注