//2020年7月20日22:29:15   做了得有1 h +，哈 （不小心看了标签，知道了可以直接暴搜hh）
//2020年7月22日10:43:46  答案要求：（1）步数最少；（2）字典序最小。
//第二点我没考虑到，但是碰巧OK了，下次要考虑周全~
//感觉我的代码比y总的更简洁一些

// y总位运算写法                               1分钟前   Accepted    7054 ms     C++ 普通
// y总数组写法                                 2分钟前   Accepted   10566 ms    C++ 普通
// 我的写法（不开vector<PII>,直接记录op即可）  3分钟前   Accepted    3173 ms     C++ 普通

//2020年7月22日10:56:27 我猜想这时间差是vector<PII>拖慢的，把y总的位运算代码按我的思路一改（存放整型数oppp即可）
//1分钟前  Accepted    563 ms  C++ 普通
// 直接提速到500了，靓仔喔

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAX = 1 << 16;
const int N = 5;

char state[N][N], backup[N][N];

void turn(int x, int y)
{
    for (int i = 0; i < 4; i ++ )   //同行、同列状态全部改变
    {
        for (int j = 0; j < 4; j ++ )
        {
            if (i == x || j == y)
            {
                if (state[i][j] == '+') state[i][j] = '-';
                else state[i][j] = '+';
            }
        }
    }
}

bool check()
{
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            if (state[i][j] == '+') return false;   //一个未打开，则打开失败
    return true;
}

int main()
{
    int ans = 999, cnt = 0, oppp = 0;
    for (int i = 0; i < 4; i ++ ) scanf("%s", state[i]);
    memcpy(backup, state, sizeof(state));   //备份

    for (int op = 0; op < MAX; op ++ )
    {
        cnt = 0;
        for (int i = 0; i < 16; i ++ )
        {
            //位运算操作，第i位为1则改变状态
            if ( (op >> i) & 1  == 1)
            {
                turn( i / 4, i % 4 );
                cnt ++ ;
            }
        }
        if (check()) ans = min(cnt, ans), oppp = op;

        memcpy(state, backup, sizeof backup);
    }

    if (ans != 999) 
    {
        cout << ans << endl;
        for (int i = 0; i < 16; i ++ )
        {
            if ((oppp >> i) & 1  == 1) printf("%d %d\n", i / 4 + 1, i % 4 + 1);
        }
    }
    return 0;
}

把y总的位运算写法改了一下，AC时间563ms
优化思路：不用vecctor存放中间结果以及答案，直接记录操作的二进制数即op的值即可

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// typedef pair<int,int> PII;
const int N = 4, INF = 100;

int change[N][N];

int get(int x, int y)
{
    return x * N + y;
}

int main()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
        {
            for (int k = 0; k < N; k ++ ) change[i][j] += (1 << get(i, k)) + (1 << get(k, j));
            change[i][j] -= 1 << get(i, j);
        }

    int state = 0;
    for (int i = 0; i < N; i ++ )
    {
        string line;
        cin >> line;
        for (int j = 0; j < N; j ++ )
            if (line[j] == '+')
                state += 1 << get(i, j);
    }

    int res = 10000;
    int oppp = 10000;
    // vector<PII> path;
    for (int i = 0; i < 1 << 16; i ++ )
    {
        int now = state;
        int cnt = 0;
        // vector<PII> temp;
        for (int j = 0; j < 16; j ++ )
            if (i >> j & 1)
            {
                int x = j / 4, y = j % 4;
                now ^= change[x][y];
                cnt ++ ;
                // temp.push_back({x, y});
            }
        // if (!now && (path.empty() || path.size() > temp.size())) path = temp;
        if (!now && cnt < res) res = cnt, oppp = i;
    }

    // cout << path.size() << endl;
    // for (auto &p : path)
    //     cout << p.first + 1 << ' ' << p.second + 1 << endl;

    if (res != 10000) 
    {
        cout << res << endl;
        for (int i = 0; i < 16; i ++ )
        {
            if ((oppp >> i) & 1  == 1) printf("%d %d\n", i / 4 + 1, i % 4 + 1);
        }
    }
    return 0;
}