AcWing 95 费解的开关
2024-09-03 07:22:03
前言
博客咕咕咕了好久了,是时候写一下了
题目链接
思路
首先可以看出
1.每一个位置顶多只会操作一次。因为如果操作两次的话,相当于不操作,必然是不满足最优解
2.在一套方案中,操作的顺序无关紧要。
3.如果我们确定了第I行的操作方案的话,那么后面的行数都可以依此递推,下面给出一个详细的解答。
11011
10110
01111
11111
比如说这个例子,如果我们确定了第1行,那么第二行所有的0(坐标:a[i][j])
都只能是第三行a[i+1][j]来修改了,因为如果你第二行修改的话,那么第一行将会打乱,下面每一行依此类推。
然后再利用状态压缩,就可以了
代码
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];
void read() {
getchar();
for (i=1; i<=5; i++) {
for (j=1; j<=5; j++) {
char ch=getchar();
b[i][j]=ch-'0';
}
getchar();
}
}
int main() {
int n;
cin>>n;
while(n--) {
read();
for (i=0; i<=(1<<5); i++) {
for (j=1; j<=5; j++) {
for (k=1; k<=5; k++)
a[j][k]=b[j][k];
}
int ans=0;
for (j=1; j<=5; j++)
if (i>>(j-1) & 1) {
ans++;
a[1][j-1]^=1,a[1][j+1]^=1,a[1][j]^=1,a[2][j]^=1;
}
for (j=1; j<=4; j++)
for (k=5; k>=1; k--)
if (!a[j][k]) {
ans++;
a[j][k]^=1,a[j+2][k]^=1,a[j+1][k]^=1,a[j+1][k+1]^=1,a[j+1][k-1]^=1;
}
bool ok=true;
for (j=1; j<=5; j++)
for (k=1; k<=5; k++)
if (!a[j][k])
ok=false;
if (ok)
ans1=min(ans1,ans);
}
if (ans1>6)
cout<<-1<<'\n';
else
cout<<ans1<<'\n';
ans1=1e10;
}
return 0;
}
最新文章
- c#线程带参数
- jQuery导入Eclipse后报错解决方法
- Html 之div+css布局之css选择器
- 浅析.NET泛型
- iOS - Swift NSTimer		定时器
- 用javacsv API 来操作csv文件
- usb cdc 协议
- 【转】HTML中A标签与click事件的前世今生
- Linux read/write fread/fwrite两者区别
- 读取和导出下载 excel 2003,2007 资料
- 用 Hexo + Github 搭建自己的博客
- QBlog V2.5 源码开放下载(ASP.NET 番外系列之开端)
- JavaWeb学习笔记五 会话技术Cookie&;Session
- 7-20 jquery遍历节点,bootstrap模态框绑定事件和解绑,mock.js,model.urlroot,id,打基础
- sql转百分比并保留两位小数
- (PMP)第5章-----项目范围管理
- Python 之 __new__() 方法与实例化(转)
- 前端html5/css基础知识
- 获取设备IP地址
- selenium+python 自动化