暴力枚举法,一共65536种可能,利用位运算表示。
开一个vector记录和更新路径。
C++ 代码如下:
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
char map0[4][4],backup[4][4];
int path[1000][1000];
typedef pair<int,int> PII;
vector<PII> v(0);
void turn_one(int x,int y){
if(backup[x][y]=='+') backup[x][y]='-';
else backup[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(){
int res=100000;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
cin>>map0[i][j];
}
}
for(int op=0;op<65536;op++){
int step=0;
memcpy(backup, map0, sizeof(map0));
for(int i=0;i<16;i++){
if(op>>i&1){
turn_all(i/4,i%4);
step++;
}
}
bool flag=true;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(backup[i][j]=='+'){
flag=false;
break;
}
}
}
if(flag){
if(step<res){
v.clear();
for (int i=0;i<16;i++) {
if (op>>i&1){
v.push_back(make_pair(i/4+1, i%4+1));
}
}
}
res=min(res,step);
}
}
cout<<res<<endl;
for(int i=0;i<v.size();i++){
cout<<v[i].first << " " <<v[i].second<<endl;
}
return 0;
}