思路：
1 题目是4*4的矩阵，数据范围小，考虑暴力枚举
2 对矩阵标号
0 1 2 3
4 5 6 7
8 9 10 11
12 14 14 15
3 总共有16个位置，每一个位置要么选，要么不选，所以情况有2^16种，我们采用二进制枚举，从0~2 ^16-1,每一个整数看他的16位二进制数，对应位上有1就选。例如1二进制为：0000 0000 0000 0001，只有第一个位置有1，那么我们选第一个位置，把对应的行，对应的列改变 .
4因为是从0枚举到2^16-1,所以得到的答案满足：
细节见代码
AC代码：
//目标：全部变成减号
#include<bits/stdc++.h>
using namespace std;
const int N = 6;
char s[N][N];
char tmp[N][N];
typedef pair<int,int> PII;
typedef vector<PII> vec;
void change(int x,int y)
{
for(int i=0;i<4;i++)
{
if(tmp[x][i]=='+') tmp[x][i] = '-';
else if(tmp[x][i]=='-') tmp[x][i]='+';
if(tmp[i][y]=='+') tmp[i][y]='-';
else if(tmp[i][y]=='-') tmp[i][y]='+';
}
if(tmp[x][y]=='+') tmp[x][y]='-';
else tmp[x][y]='+';
return ;
}
//检查是不是全部变成“-”了
bool check()
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(tmp[i][j]!='-') return false;
}
}
return 1;
}
int main()
{
//输入：
for(int i=0;i<4;i++) scanf("%s",s[i]);
//有16个位置，每一个要么选要么不选
//从0~2^16-1枚举
int e = 1<<16;
vec ans;
for(int k=0;k<e;k++)
{
//将s的内容拷贝到tmp
memcpy(tmp,s,sizeof s);
vec tp;
for(int i=0;i<16;i++)
{
if(k>>i&1) //取数字k的第i位，从第0位开始计算
{
//i/4是行，i%4是列
change(i/4,i%4);
tp.push_back({
i/4,i%4});
}
}
if(check())
{
if(ans.empty()||ans.size()>tp.size()) ans=tp;
}
}
printf("%d\n",ans.size());
//注意输出的时候要+1
for(int i=0;i<ans.size();i++)
{
printf("%d %d\n",ans[i].first+1,ans[i].second+1);
}
return 0;
}
京公网安备 11010502036488号