算法

(暴力枚举)

用一个16位二进制数存储当前局面，用0~2^16-1间的每个数表示出每一种做法，然后用位运算得到结果
代码优化的地方大概是不用数组/队列存储结果，每次对行/列操作也用位运算简化

时间复杂度 O(2^16 * 16)

C++ 代码

#include<iostream>
using namespace std;
const int row[5] = {0x000f,0x00f0,0x0f00,0xf000},
          col[5] = {0x1111,0x2222,0x4444,0x8888};

void op(int &x,int i,int j)
{
    x ^= row[i];
    x ^= col[j];
    x ^= 1 << (4*i+j);
}

int main()
{
    int res=0,min_cnt=0x3f3f,ans;
    char g[4][5];
    for(int i = 0 ; i < 4 ; i ++)
    {
        cin >> g[i];
        for(int j = 0 ; j < 4 ; j ++)
            if(g[i][j]=='-')
                res += 1 << (4*i+j);
    }
    for(int k = 0 ; k < 1<<16 ; k ++)
    {
        int tmp = res,cnt = 0;
        for(int w = 0 ; w < 16 ; w ++)
        {
            if((k>>w)&1)
            {
                op(tmp,w>>2,w%4);
                ++cnt;
            }
        }
        if(cnt<min_cnt&&tmp==0xffff)  
        {
            min_cnt = cnt;
            ans = k;
        }
    }
    cout << min_cnt << endl;
    for(int i = 0 ; i < 16 ; i ++)
        if((ans>>i)&1)
            cout << i/4 + 1 << ' ' << i%4 + 1 << endl;
}