蓝桥杯刷题
作者:
Maveric
,
2024-03-19 17:11:59
,
所有人可见
,
阅读 19
//哈哈哈哈哈哈起飞
//第一次自己写出来dfs,写了一个小时。终于还是调对了。中间Segmentation Fault调了好久
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5;
vector<int> q,res;
char g[N][N];
int ans = 0x3f;
bool flag;
void turn(int x, int y)
{
if(g[x][y] == '-') g[x][y] = '+';
else g[x][y] = '-';
}
void turn_all(int u)
{
int x,y;
if(u%4 == 0) x = u/4, y = 4;
else x = u/4 + 1, y = u%4;
for(int i = 1; i <= 4; i ++)
{
turn(x,i);
turn(i,y);
}
turn(x,y);
}
bool check()
{
bool ff = true;
for(int i = 1; i <= 4; i ++)
for(int j = 1; j <= 4; j ++)
if(g[i][j] == '+')
ff = false;
return ff;
}
void dfs(int u,int cnt)
{
if(u == 17) return;
if(cnt >= ans) return;
if(u==16 && check() && ans >= cnt)
{
ans = cnt;
res = q;
return;
}
q.push_back(u+1);
turn_all(u+1);
dfs(u+1,cnt++);
q.pop_back();
turn_all(u+1);
dfs(u+1,cnt);
}
int main()
{
for(int i = 1; i <= 4; i ++)
for(int j = 1; j <= 4; j ++)
cin>>g[i][j];
dfs(0,0);
cout<<res.size()<<endl;;
for(int i = 1; i <= res.size(); i ++)
{
auto t = res[i-1];
int x,y;
if(t%4 == 0) x = t/4, y = 4;
else x = t/4 + 1, y = t%4;
cout<<x<<' '<<y<<endl;
}
}