这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
谁说这道题简单?是水题?
又让我郁闷了。
思路:枚举,BFS,位操作
分析:要求输入一个44的棋盘,考虑状态是否全为黑或者全为白,状态共有2^16种,联系棋盘是44,可以想到用位来压缩状态。
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
自定义难度:★★★☆☆
代码:
// POJ 1753
// Author: Tanky Woo
#include
#include
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 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;
}