dfs暴力枚举
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
char g[5][5];
typedef pair<int,int> PII;
vector<PII> step;
void turn(int x,int y){//开关
for(int i=0;i<4;i++){
if(g[x][i]=='+') g[x][i]='-';
else g[x][i]='+';
}
for(int i=0;i<4;i++){
if(g[i][y]=='+') g[i][y]='-';
else g[i][y]='+';
}
if(g[x][y]=='+') g[x][y]='-';
else g[x][y]='+';
}
void dfs(int u){
int x=u/4,y=u%4;//获取横纵坐标
if(u==16){
bool on=true;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(g[i][j]=='+')
on=false;
if(on){
cout<<step.size()<<endl;
for(int i=0;i<step.size();i++)
printf("%d %d\n",step[i].first,step[i].second);
}
return;
}
turn(x,y);//选择对x,y操作
step.push_back({x+1,y+1});//将选择的坐标存到vector中
dfs(u+1);//进行下一层枚举
turn(x,y);//恢复现场
step.pop_back();//将之前存的踢出来
dfs(u+1);//进行下一层枚举
}
int main(){
for(int i=0;i<4;i++) cin>>g[i];
dfs(0);//将4*4的矩阵压成16的一维矩阵
return 0;
}
腻害
Orz…
可能我太菜了把,写的比较麻烦 哈哈