本题采用二进制的写法

C++ 代码

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

using namespace std;

typedef pair<int, int> PII;

const int N = 5;

char g[N][N], back[N][N];

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

void turn_one(int x, int y)
{
    if (g[x][y] == '+') g[x][y] = '-';
    else g[x][y] = '+';
}

void turn_all(int x, int y)
{
    for (int i = 0; i < 4; i ++ )
        turn_one(x, i), turn_one(i, y);

    turn_one(x, y);
}

int main()
{
    for (int i = 0; i < 4; i ++ )
        cin >> g[i];
    vector<PII> res;

    // /1<<16 表示将数字1的二进制表示向左移动16位。
    for (int op = 0; op < 1 << 16; op ++ )
    {
        vector<PII> temp;
        memcpy(back, g, sizeof back);
        for (int i = 0; i < 4; i ++ )
            for (int j = 0; j < 4; j ++ )
                if (op >> get(i, j) & 1)
                {
                    temp.push_back({i, j});
                    turn_all(i, j);
                }

        bool has_close = false;

        for (int i = 0; i < 4; i ++ )
            for (int j = 0; j < 4; j ++ )
                if (g[i][j] == '+')
                    has_close = true;

        if (has_close == false)
        {
            if (res.empty() || res.size() > temp.size())
                res = temp;
        }

        memcpy(g, back, sizeof back);
    }

    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i ++ )
        cout << res[i].first + 1 << ' ' << res[i].second + 1 << endl;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla