AcWing 116. 飞行员兄弟——递归实现指数型枚举--模板
原题链接
简单
作者:
编号002
,
2024-04-19 12:36:43
,
所有人可见
,
阅读 1
//每个点,选 与 不选 --> 子集
#include<iostream>
#include<vector>
using namespace std;
const int N=10;
char g[N][N];
bool state[N][N];
int min_cnt=100000;
vector<pair<int,int>>ans; //答案容器
void turn(int x,int y)
{
for(int i=1;i<=4;i++) //此操作会将点(x,y)变化两次,相当于没有变化
{
if(g[x][i]=='+')g[x][i]='-';
else g[x][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 x,int y,int cnt)
{
if(y==5) //经典的移动操作
{
x++;
y=1;
}
if(x==5&&y==1) //注意结束条件,不是x==4&&y==4,如果是if(x==4&&y==4)那么直接return,之后的dfs(4,4,cnt)将不会继续进行,没有选择这个点
{
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
if(g[i][j]!='-')return;
if(cnt<min_cnt)
{
min_cnt=cnt;
ans.clear(); //清空vector
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
if(state[i][j])ans.push_back({i,j});
}
return;
}
//不选
state[x][y]=0; //可省略
dfs(x,y+1,cnt);
//选
state[x][y]=1;
turn(x,y);
dfs(x,y+1,cnt+1);
state[x][y]=0; //回溯,为得到所有可行的解
turn(x,y);
}
int main()
{
for(int i=1;i<=4;i++)cin>>g[i]+1; //g[i]+1,是地址
dfs(1,1,0);
cout<<ans.size()<<endl;
for(auto t:ans)cout<<t.first<<' '<<t.second<<endl;
return 0;
}