飞行员兄弟
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
思考
此题可以先看注释，不懂得可以问我，我看到回复，日后复习到它我写详细的证明
import java.util.*;
import java.io.*;
public class Main {
static int N = 5;
static char g[][] = new char [N][N];
static char backup[][] = new char [N][N];
public static class Pii {
int x, y;
public Pii(int x, int y){
this.x = x;
this.y = y;
}
}
public static int get(int x, int y){
return 4 * x + y;
}
public static void turn_one(int x, int y){
if (g[x][y] == '+') g[x][y] = '-';
else g[x][y] = '+';
}
public static void turn_all(int x, int y){
for(int i=0; i<4; i++){
turn_one(x, i);
turn_one(i, y);
}
turn_one(x, y);
}
public static void main(String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i=0; i<4; i++)
g[i] = br.readLine().toCharArray();
//还原原型的备份数组
for(int i=0; i<4; i++) backup[i] = g[i].clone();
// 存储最终方案的操作
List <Pii> res = new ArrayList<Pii>();
// 枚举所有方案
for(int op=0; op < 1<<16; op++){
// 存储待定答案数组
List <Pii> temp = new ArrayList<Pii>();
// 枚举16个位置按方案的情况进行操作
for(int i=0; i<4; i++)
for(int j=0; j<4; j++)
if((op >> get(i, j) & 1) == 1){
// 加入temp队列 并打开相应行列开关
// 这里加1因为答案坐标是从1开始
temp.add(new Pii(i+1, j+1));
turn_all(i, j);
}
// 判断灯泡是否全部全亮
boolean dark = false;
for(int i=0; i<4; i++)
for(int j=0; j<4; j++)
if (g[i][j] == '+'){
dark = true;
break;
}
if (!dark)
if (res.isEmpty() || temp.size() < res.size()) res = temp;
// 每个op使用过后需要把g变回最初的样子
for(int i=0; i<4; i++) g[i] = backup[i].clone();
}
// 没说无解可猜想必定有解
System.out.println(res.size());
for(int i=0; i<res.size(); i++)
System.out.println(res.get(i).x + " " + res.get(i).y);
}
}
兄弟能不能帮忙看看我这哪里错了
#include<bits/stdc++.h> using namespace std; char g[6][6]; char backup[6][6]; typedef pair<int,int> pii; vector<pii>res;//储存操作次数最少的方案 void turn(int r,int c) { for(int i=1;i<=4;i++) { if(g[r][i]=='+') g[r][i]=='-'; else g[r][i]=='+'; if(g[i][c]=='+') g[i][c]=='-'; else g[i][c]=='+'; } } bool check()//判断所有把手是否全部打开 { for(int i=1;i<=4;i++) for(int j=1;i<=4;j++) { if(g[i][j]=='+')//存在一个没有打开的把手 return false; } return true; } int main() { for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) scanf("%c",&g[i][j]); for(int op=0;op<65536;op++)//每个把手都可以进行操作或者不进行操作2种状态，共2^16种情况，用十进制数字0~2^16-1分别代表每种情况 { vector<pii>temp;//暂时保存操作 int step=0; memcpy(backup,g,sizeof g);//备份 for(int i=15;i>=0;i--)//每个十进制数化成二进制有16个位代表每种情况下的16个把手,每位是0或1，1代表对把手进行操作,0表示不操作 { if(op>>i&1)//第16-i号把手是否为1 { int t=16-i; int r=(t-1)/4+1;//16-i号把手所在行 int c=(t-1)%4+1;//16-i号把手所在列 turn(r,c);//进行操作 temp.push_back({r,c});//保存此操作 } } if(check())//对每种情况检查是否所有把手都已打开 { if(res.size()==0||res.size()>temp.size()) res=temp;//储存操作次数最少的 } memcpy(g,backup,sizeof g);//还原 } cout<<res.size()<<endl; for(auto t:res) cout<<t.first<<' '<<t.second<<endl; }