题意:

在4*4的棋盘里有16个可黑可白的棋,每轮游戏可以选择将一个棋及其上下左右相邻的棋的颜色取反(最多五个最少三个),所有棋面颜色相同时游戏结束,求最少进行几轮游戏后游戏结束

思路:

对任意的一个棋子进行两次翻转操作是无意义的,负负得正,因此一个棋最多只翻一次,可以采取枚举

我们从上至下(当然你也可以换个方向),一行一行的将棋子翻到相同的颜色(比如说我们现在要把它们全部翻成白色),我们记0为黑,1为白

假如前两行的棋子是0101,1111,那么为了让第一行的棋子全都变成1,我们需要对第二行第一个、第二行第三个,也就是对第一行的0下面的那个棋子进行反转
这样翻转以后,只需要再判断一下最后一行是否全是白色(游戏是否能被正确的结束)即可

但是这样解题是依据第一行一开始的颜色来进行推算的,而我们又可以对第一行的棋进行翻转,所以我们需要列出第一行的所有翻转情况,并向下推算需要翻转的次数,找出最小的次数即可

代码:

*代码用二维数组会更好看一些,但这题我尝试了一下位运算
*下面给的代码里注释了display之类的代码,是debug时候用的
*代码写的又臭又长,但也写的比较仔细了,看懂应该不难 嘤嘤嘤

#include <iostream>

using namespace std;

/*返回map中第row行第column个棋的颜色*/
inline int getColor(int row, int column, int map) {
    int gap = 16 - (((row - 1) * 4) + column);    //位运算时左移右移的位数
    return (map & (1 << gap)) >> gap;
}

//输出当前棋盘的图
inline void display(int map) {
    cout << map << ":" << endl;
    for (int i = 15; i >= 0; --i) {
        cout << ((map >> i) & 1);
        if (i % 4 == 0)cout << endl;
    }
    cout << endl;
}

//反转(row,column)上的棋
inline void reverse(int row, int column, int &map) {
    int gap = 16 - (((row - 1) * 4) + column);
    int reverse = 1 << gap;
    //反转当前的棋
    map = map ^ reverse;
    //反转它下面的棋
    if (row != 4)map ^= (reverse >> 4);
    //反转它上面的棋
    if (row != 1)map = map ^ (reverse << 4);
    //反转它左面的棋
    if (column != 1)map = map ^ (reverse << 1);
    //反转它右面的棋
    if (column != 4)map = map ^ (reverse >> 1);

}

/*
 * 将棋盘中的黑色全部翻成白色
 * 并返回最少翻转次数*/
int flipGame(int originMap) {
    int minRes = 17;
    /*
     * 先将第一行的反转情况遍历,从0000-1111共有16种可能(0为不反转,1为反转)
     * */
    for (int i = 0; i < 16; ++i) {
        int res = 0;    //反的次数
        int copyMap = originMap;
//        cout<<"CopyMap:\n";
//        display(copyMap);
        //反转第一行
        for (int j = 3; j >= 0; --j) {
            if ((1 << j) & i) {  //根据二进制i逐位判断是否需要反转
                res++;
                reverse(1, 4 - j, copyMap);
            }
        }
//        cout<<"i="<<i<<"  遍历后的map:\n";
//        display(copyMap);
        //对剩下的棋进行反转
        for (int row = 1; row <= 3; ++row) {
            for (int column = 1; column <= 4; ++column) {
                //如果当前的棋是黑色则反转它 下面 的那个棋(让当前的棋变成白色)
                if (getColor(row, column, copyMap) == 0) {
                    res++;
                    reverse(row + 1, column, copyMap);
//                display(copyMap);
                }
            }
        }
        //如果棋盘成功被全部翻成白色,记录翻的次数
        if ((copyMap & 15) == 15) {
            minRes = min(res, minRes);
        }
//        cout<<"---------------------------"<<endl;
    }
    return minRes;
}

int main() {
    char temp;   //工具人变量
    int map = 0;  //游戏棋盘,用二进制表示,0代表黑,1代表白
    for (int i = 0; i < 16; ++i) {
        cin >> temp;
        if (temp == 'b')map = map << 1;
        else if (temp == 'w')map = (map << 1) + 1;
    }

    int a, b;
    a = flipGame(map);
//    cout << a << endl;

    //map中黑白反转,0代表白,1代表黑,再进行一次游戏并记录最小反转次数
    map = map ^ ((1 << 16) - 1);

    b = flipGame(map);
//    cout << b << endl;
    if (a == 17 && b == 17) {
        cout << "Impossible" << endl;
        return 0;
    }
    cout << min(a, b);
}

第52行 根据二进制 i 逐位判断是否需要反转 的补充说明:
对于第一行棋子,我们记翻转情况0为不翻转,1为翻转,那么for循环i=0到i<16就将i从0000遍历到1111,列举所有情况。

下面52行的for和下面的if:用for和左移,让0001,0010,0100,1000和i进行位与操作,如果得到的不是0,即代表第一行上那一个棋子需要进行翻转操作