题目链接
题意：就是用最少的改变方法把所有的状态都变成-，改变一个状态，对应的行和列都改变
整体思路就是暴力深搜，一个位置2个可能，变或者不变，注意回溯状态
#include<iostream> #include<algorithm> #include<map> #include<string> #include<vector> using namespace std; const int INF=1<<29; int maxn=INF; int ma[10][10]={0}; int a[10][10]={0}; typedef struct node{ vector<int> v; }node; node no[20]; int pd(){ int sum=0; for(int i=0;i<4;i++){ for(int j=0;j<4;j++) if(ma[i][j]==0) return 0; } return 1; } void change(int i,int j){//改变行列 ma[i][j]=!ma[i][j]; for(int k=0;k<4;k++){ ma[i][k]=!ma[i][k]; ma[k][j]=!ma[k][j]; } } void dfs(int i,int j,int sum){ if(pd()){ if(sum<maxn) {//找到任意一组数据就可以，用的vector存储坐标。最后输出 maxn=sum; for(int k=0;k<4;k++) for(int l=0;l<4;l++) if(a[k][l]==1) no[maxn].v.push_back(k),no[maxn].v.push_back(l); } return; } if(j+1<=3){ a[i][j+1]=0;//不改变标记为0 dfs(i,j+1,sum); a[i][j+1]=1;//改变标记为1 change(i,j+1); dfs(i,j+1,sum+1); change(i,j+1); a[i][j+1]=0;//注意回溯状态 } else if(i+1<=3){ a[i+1][0]=0; dfs(i+1,0,sum); a[i+1][0]=1; change(i+1,0); dfs(i+1,0,sum+1); change(i+1,0); a[i+1][0]=0; } } int main(){ for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ char c; cin>>c; if(c=='-') ma[i][j]=1; } } dfs(0,0,0);//第一个状态不改变 //第一个状态改变 a[0][0]=1; change(0,0); dfs(0,0,1); cout<<maxn<<endl; for(int i=0;i<no[maxn].v.size();i+=2){ cout<<no[maxn].v[i]+1<<" "<<no[maxn].v[i+1]+1<<endl; } return 0; }另外附一些例子：
-+-- ++++ -+-- -+-- 1 2 2 ++++ ++++ ++++ ++++ 16 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4 +--+ +--- +++- +++- 3 1 1 2 2 2 3 +--- -+++ ++++ ++++ 4 1 1 2 2 2 3 2 4 -+++ ++++ -+++ -+++ 3 2 2 2 3 2 4 ++-+ ++++ ++++ ++++ 9 2 1 2 2 2 4 3 1 3 2 3 4 4 1 4 2 4 4
