题目：飞行员兄弟

• 开关问题：
  （1）每个开关只按一次
  （2）顺序无关紧要

题目

代码部分

方法一：

#include <bits/stdc++.h>
using namespace std;
char c[10][10];
typedef pair<int,int> PII;
vector<PII> ans,p;
void turn(int x,int y)
{
    if(c[x][y]=='+') c[x][y]='-';
    else c[x][y]='+';
}
void turn_open(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        turn(x,i);
        turn(i,y);
    }
    turn(x,y);
}
void dfs(int x,int y)
{
    if(y==4) x++,y=0;
    if(x==4)
    {
        int flag=0;
        for(int i=0;i<4;i++)
            for(int j=0;j<=4;j++){
                if(c[i][j]=='+')
                {
                    flag=1;
                    break;
                }
        }
        if(!flag)
        {
            if(ans.empty()||p.size()<ans.size())
            {
                ans=p;
            }
        }
        return;
    }
    // 不改变状态
    dfs(x,y+1);
    // 改变状态
    turn_open(x,y);
    p.push_back({x,y});
    dfs(x,y+1);
    p.pop_back();
    turn_open(x,y);
}
int main ()
{
    for(int i=0;i<4;i++) scanf("%s",c[i]);
    dfs(0,0);
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i].first+1<<" "<<ans[i].second+1<<endl;
    }
    return 0;
}

方法二：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> nums;
char c[4][4],s[4][4];//s数组用来备份 
void turn(int x,int y)
{
	if(c[x][y]=='+') c[x][y]='-';
	else c[x][y]='+';
}
void turn_open(int x,int y)
{
	for(int i=0;i<4;i++)
	{
		turn(x,i);
		turn(i,y);
	}
	turn(x,y);
}
int get(int x,int y)
{
	return x*4+y;
}
int main ()
{
	for(int i=0;i<4;i++) scanf("%s",c[i]);
	
	for(int i=0;i< 1<<16;i++)
	{
		vector<PII> p;
		memcpy(s,c,sizeof c); // 备份 
		for(int x=0;x<4;x++) 
		{
			for(int y=0;y<4;y++)
			{
				if(i >> get(x,y)&1)
				{
					p.push_back({x,y});
					turn_open(x,y);
				}
			}
		}
		int flag=0;
		for(int i=0;i<4;i++)
		{
			for(int j=0;j<4;j++)
			{
				if(c[i][j]=='+') flag=1;
			}
		}
		if(!flag)
		{
			if(nums.empty()||p.size()<nums.size()) nums=p;
		}
		memcpy(c,s,sizeof s);
	}
	cout<<nums.size()<<endl;
	for(int i=0;i<nums.size();i++)
	{
		cout<<nums[i].first+1<<" "<<nums[i].second+1<<endl; 
	}
	return 0;
}