acwing 116. 飞行员兄弟
2024-09-06 09:14:47
地址 https://www.acwing.com/problem/content/118/
“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有16个把手的冰箱。
已知每个把手可以处于以下两种状态之一:打开或关闭。
只有当所有把手都打开时,冰箱才会打开。
把手可以表示为一个4х4的矩阵,您可以改变任何一个位置[i,j]上把手的状态。
但是,这也会使得第i行和第j列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行,每行包含四个把手的初始状态。
符号“+”表示把手处于闭合状态,而符号“-”表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数N,表示所需的最小切换把手次数。
接下来N行描述切换顺序,每行输入两个整数,代表被切换状态的把手的行号和列号,数字之间用空格隔开。
数据范围
1≤i,j≤4
输入样例:
-+--
----
----
-+--
输出样例:
6
1 1
1 3
1 4
4 1
4 3
4 4
注意:如果存在多种打开冰箱的方式,则按照优先级整体从上到下,同行从左到右打开。
题解 没有剪枝等捷径 就是考核位运算
使用int change[4][4] 记录任意一个按钮点击后的变化
0~1<<16 二进制代表各种按钮的按法组合 然后遍历尝试
代码如下
#include <iostream>
#include <string>
#include <vector> using namespace std; typedef pair<int,int> PII; int change[][]={}; int get(int x,int y){
return x*+y;
} int main()
{
int state = ;
for(int i = ;i < ;i++){
string tmpStr;
cin >> tmpStr;
for(int j = ; j < tmpStr.size();j++){
if(tmpStr[j] == '+'){
state += <<get(i,j);
}
}
} //制作每次点击某个开关后的变化表格
for(int i =;i < ;i++){
for(int j = ; j < ;j++){
for(int k = ; k < ;k++){
change[i][j] += << get(i,k);
change[i][j] += <<get(k,j);
}
//选择的点回增加两次,减少1
change[i][j] -= << get(i,j);
}
} vector<PII> res;
//遍历各种可能的点击开关的方案 16个按钮选出任意N个点击 从0-16个的排列组合就是0~ 1<<16;
for(int k = ;k < << ;k++){
int now = state;
vector<PII> path;
//当前选择的点击方案 点击了那些按钮
for(int i = ; i< ;i++){
if(k >> i & ){
//该按钮按下了
int x = i/,y = i%;
now ^= change[x][y];
path.push_back({x,y});
}
if(!now && ( res.empty() || res.size() > path.size() ))
res = path;
}
} cout << res.size() << endl;
for(auto p : res)
cout << p.first + << ' ' << p.second+ << endl; return ;
}
最新文章
- Linux 文件描述符和重定向
- Android 友盟分享躺过的几个坑,大坑,坑爹啊
- HTML5+CSS3学习目录
- 在存储过程中执行3种oracle循环语句
- RPi 2B Raspbian SD卡内部架构
- 制作qtopia-2.2.0和qt4文件系统
- 《Windows编程零基础学》第零节
- Python偏函数实例
- 【SSH2(实用文章)】--Struts2文件上传和下载的例子
- 用python开发调试器——起始篇
- Java课程总结
- Jmeter的安装和启动错误总结,出现unable to access jarfile apachejmeter.jar error value=1错误处理
- mysql常用压测工具
- DevExpress ASP.NET v18.2新功能详解(四)
- spring 整合Junit学习
- Java中 i++ 是线程安全的么?为什么?
- Win &; Mac 系统之间U盘传递的U盘文件格式选取问题
- 如何查看ETW Trace?
- 你知道吗?衡量 Web 性能的几个关键指标
- jquery1.7+里不能用checked获得checkbox的属性
热门文章
- PlayJava Day029
- Ligg.EasyWinApp-102-Ligg.EasyWinForm:Function--ControlBox、Tray、Resize、Menu
- 请确保二进制储存在指定的路径中,或者调试他以检查该二进制或相关的DLL文件
- Java_枚举Enum基本使用
- s3c2440裸机-代码重定位、清bss的改进和位置无关码
- PyCharm 快捷键失效解决办法
- Java学习关于setContentPane()和getContentPane()的应用
- yii2 提示
- 了解angularjs中的生命周期钩子函数$onInit,$onChange,$onDestory,$postLink
- 请求时发送OPTIONS请求