Tanky WooRSS

POJ 1753 Flip Game

06 Jul 2010
这篇博客是从旧博客 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

 

   Time: 16MS

   Language: C++

 

   Result: Accepted

自定义难度:★★★☆☆

代码:

 

 // 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;
}