filpgame 翻转游戏

思路：

一个点翻转影响的范围是有限的。

以3x3的游戏为例。

第3行翻转一个点，只会影响到第三行和第二行，影响不了第一行，所以第一行的状态仅与第一行的翻转情况和第二行的翻转情况有关。

那么如果我们随意给定一个第一行的翻转情况，要想让第一行都翻转为1，那么只能控制第二行来间接翻转第一行，从而让第一行变为1.

可知一旦第一行的翻转情况确定下来，那么第二行为了让第一行全部为1，那么第二行的翻转情况也就确定了。

同理第三行为了让第二行为1，那么第三行的结果也就确定了。

所以问题就变为了如何找到一个合适的第一行的翻转情况，让整个棋盘为1.

那么要做的就是遍历第一行所以的翻转情况。

在线游戏地址：https://clicking.toys/flip-grid/neat-nine/3-holes/

#include <cstdio>
#include <iostream>

void filpRow(bool* state, bool* ans, int row, int column, int opt, int nowRow) {
    int index = nowRow * column;
    for (int i=0;i<column;++i) {
        ans[index+i] = (opt & 1);
        opt = opt >> 1;
    }
}

void getRowAns(bool* state, bool* ans, int column, int nowRow) {
    int index = nowRow * column;
    int i1 = (nowRow - 2) * column;
    int i2 = (nowRow - 1) * column - 1;
    int i3 = (nowRow - 1) * column;
    int i4 = (nowRow - 1) * column + 1;

    for (int i=0;i<column;++i) {
        ans[index] = !state[i3];
        ans[index] ^= ans[i3];
        if (nowRow >= 2) ans[index] ^= ans[i1];
        if (i > 0) ans[index] ^= ans[i2];
        if (i < column-1) ans[index] ^= ans[i4];
        ++index;
        ++i1;
        ++i2;
        ++i3;
        ++i4;
    }
}

void show(bool* b, int row, int column) {
    for (int i=0;i<row;++i) {
        int index = i * column;
        for (int j=0;j<column;++j) {
            printf("%d ", b[index + j]);
        }
        printf("\n");
    }
}

void showFinalState(bool* state, bool* ans, int row, int column) {
    int s1 = -column;
    int s2 = -1;
    int s3 = 0;
    int s4 = 1;
    int s5 = column;
    int index = 0;
    for (int i=0;i<row;++i) {
        for (int j=0;j<column;++j) {
            bool fs = state[index] ^ ans[index];
            if (i > 0) fs ^= ans[s1];
            if (j > 0) fs ^= ans[s2];
            if (j < column - 1) fs ^= ans[s4];
            if (i < row - 1) fs ^= ans[s5];
            ++index;
            ++s1;
            ++s2;
            ++s3;
            ++s4;
            ++s5;
            printf("%d ", fs);
        }
        printf("\n");
    }
}

void calc(bool* state, bool* ans, int row, int column) {
    int maxOperation = (1 << column) - 1;
    int size = row * column;
    for (int opt = 0; opt <= maxOperation; ++opt) {
        // init first line ans
        //memset(ans, 0, size*sizeof(bool));
        filpRow(state, ans, row, column, opt, 0);
        // printf("after init\n");
        // show(ans, row, column);
        // calc other line
        for (int i=1;i<row;++i) {
            getRowAns(state, ans, column, i);
        }
        // check ans
        // printf("check ans\n");
        // show(ans, row, column);
        // printf("final state\n");
        // showFinalState(state, ans, row, column);
        bool flag = true;
        int index = (row - 1) * column;
        int i1 = index - column;
        int i2 = index - 1;
        int i3 = index + 1;
        for (int i=0;i<column;++i) {
            bool fs = state[index] ^ ans[index] ^ ans[i1];
            if (i > 0) fs = fs ^ ans[i2];
            if (i < column-1) fs = fs ^ ans[i3];
            if (!fs) {
                flag = false;
                break;
            }
            ++index;
            ++i1;
            ++i2;
            ++i3;
        }
        if (flag) return;
    }
}

int main() {
    bool state[] = {
        1, 1, 0,
        0, 0, 1,
        0, 1, 0,
    };
    bool ans[9];
    int row = 3;
    int column = 3;
    calc(state, ans, row, column);

    show(ans, row, column);

    return 0;
}