AcWing 116. 飞行员兄弟
原题链接
简单
作者:
锦城虽云乐
,
2024-08-22 11:31:34
,
所有人可见
,
阅读 1
和费解的开关是同类型
第一步写操作函数turn和turnall
由于要步骤,就不能枚举,要dfs
还是老规矩,最后一行不要看
由于每个位置都可以不操作,所以要进行两次dfs
#include<iostream>
#include<vector>
using namespace std;
char g[5][5];
vector<pair<int,int>>path,ret;
void turn(int x,int y)
{
if(g[x][y]=='-')
{
g[x][y]='+';
}
else
{
g[x][y]='-';
}
}
void turnall(int x,int y)
{
for(int i=0;i<4;i++)
{
turn(x,i);
turn(i,y);
}
turn(x,y);
}
bool judge()
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(g[i][j]=='+')
{
return false;
}
}
}
return true;
}
void dfs(int x,int y)
{
if(x==3&&y==4)
{
bool sign=judge();
if(sign)
{
if(ret.size()==0||path.size()<ret.size())
{
ret=path;
}
}
return;
}
if(y==4)
{
y=0;
x++;
}
turnall(x,y);
path.push_back({x,y});
dfs(x,y+1);
path.pop_back();
turnall(x,y);
dfs(x,y+1);
}
int main()
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
cin>>g[i][j];
}
}
dfs(0,0);
cout<<ret.size()<<endl;
for(auto l:ret)
{
cout<<l.first+1<<' '<<l.second+1<<endl;
}
return 0;
}