POJ 1753 Flip Game C++版

文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

帮朋友A的，广搜+位运算

Description

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:

1. Choose any one of the 16 pieces.
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).

bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:

bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

Input

The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.

Output

Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).

Sample Input

bwwb
bbwb
bwwb
bwww

Sample Output

Slyar:每次改变相邻位置，求最少步数到全部一样。这种矩阵求最少步数到某一状态一般是考虑BFS了，然后就是怎么简化题目的问题，反正就w和b这2个状态，0和1也是2个状态，所以很容易想到了位运算，16个位置看成16个2进制位就好(目的就是全1或全0)，题目要求相邻位置改变，最近看MFC的我马上想到了逻辑操作符...这里的情况是反转，所以用异或...所以算法就很容易了，提前打表求出每一位相邻位置改变后的值(把该位置连同相邻置1，其余位置置0)，然后BFS就行了，具体看注释....好久不写ACM程序了，编译错误了3次，数组越界了3次...=_=

#include <iostream>

using namespace std;

const int MAX = 65535;

// 打表，计算器就能得到...
const int ARRAY[17] = {0,
51200, 58368, 29184, 12544,
35968, 20032, 10016, 4880,
2248, 1252, 626, 305,
140, 78, 39, 19};

// 搜索队列
struct
{
    int sum;
    int step;
}Queue[MAX+1] = {0};

// 搜索标记
bool signal[MAX] = {0};

int main()
{
    char ch;
    // 初始队列为空
    int head = 0;
    int tail = 0;

    // 现在的和
    int now = 0;

    // 读入数据
    tail = 1;
    for(int i = 15; i >= 0; i--)
    {
        cin >> ch;
        // 求16个2进制位的和入队
        if (ch == 'b')
        {
            Queue[tail].sum += (1 << i);
        }
        // 滤掉换行
        if (i % 4 == 0)
        {
            cin.get();
        }
    }

    // 和已经符合要求
    if (Queue[tail].sum == 0x0000 || Queue[tail].sum == 0xFFFF)
    {
        head = tail + 1;
    }

    // 标记搜索
    signal[Queue[tail].sum] = true;

    // 队列不空
    while (head < tail)
    {
        // 出队处理
        head++;
        
        // 搜索
        for (int i = 1; i <= 16; i++)
        {
            // 依次异或打表值求和
            now = Queue[head].sum ^ ARRAY[i];
            // 和没有出现过，继续入队
            if (!signal[now])
            {
                tail++;
                Queue[tail].sum = now;
                Queue[tail].step = Queue[head].step + 1;
                signal[now] = true;

                // 找到结果
                if (now == 0x0000 || now == 0xFFFF)
                {
                    head = tail + 1;
                    break;
                }
            }
        }
    }
    // head > tail，队列就爆了，以此标记找到结果=_=
    if (head == tail + 1)
    {
        cout << Queue[tail].step << endl;
    }
    else
    {
        cout << "Impossible" << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

const int MAX = 65535;

// 打表，计算器就能得到...

const int ARRAY[17] = {0,

51200, 58368, 29184, 12544,

35968, 20032, 10016, 4880,

2248, 1252, 626, 305,

140, 78, 39, 19};

// 搜索队列

struct

{

int sum;

int step;

}Queue[MAX+1] = {0};

// 搜索标记

bool signal[MAX] = {0};

int main()

{

char ch;

// 初始队列为空

int head = 0;

int tail = 0;

// 现在的和

int now = 0;

// 读入数据

tail = 1;

for(int i = 15; i >= 0; i--)

{

cin >> ch;

// 求16个2进制位的和入队

if (ch == 'b')

{

Queue[tail].sum += (1 << i);

}

// 滤掉换行

if (i % 4 == 0)

{

cin.get();

}

// 和已经符合要求

if (Queue[tail].sum == 0x0000 || Queue[tail].sum == 0xFFFF)

{

head = tail + 1;

}

// 标记搜索

signal[Queue[tail].sum] = true;

// 队列不空

while (head < tail)

{

// 出队处理

head++;

// 搜索

for (int i = 1; i <= 16; i++)

{

// 依次异或打表值求和

now = Queue[head].sum ^ ARRAY[i];

// 和没有出现过，继续入队

if (!signal[now])

{

tail++;

Queue[tail].sum = now;

Queue[tail].step = Queue[head].step + 1;

signal[now] = true;

// 找到结果

if (now == 0x0000 || now == 0xFFFF)

{

head = tail + 1;

break;

}

// head > tail，队列就爆了，以此标记找到结果=_=

if (head == tail + 1)

{

cout << Queue[tail].step << endl;

}

else

{

cout << "Impossible" << endl;

}

return 0;

}

转载请注明：Slyar Home » POJ 1753 Flip Game C++版

@HuaiBoy 你是初中生？

free斩11年前（2012-05-10）回复

@kis2009dsh 能把高斯消元的做法发给我看下吗？

qiqijianglu12年前（2011-10-06）回复

今天在百度搜软考中级的网络，来到了这里。。。然后做poj上的题，又到了这里我觉得这还没什么，我想换个系统所以要了解一下Linux，结果又到了这里！！！！你是不是交钱给百度了啊。。。。o(╯□╰)o 膜拜Slyar哥

Paradise12年前（2011-07-30）回复

恩，听说高斯消元可以做到0ms，但是还不会啊……………………@kis2009dsh

匿名12年前（2011-05-18）回复

貌似。。。模2域上的高斯消元也行。。。

kis2009dsh13年前（2011-01-31）回复

膜拜Orz 南哥。。。 POJ上的英文题我都无视掉，初中英语还不够应付啊。

HuaiBoy13年前（2010-10-30）回复

POJ 1753 Flip Game C++版

与本文相关的文章

Hi，您需要填写昵称和邮箱！

网友最新评论 (6)