首页 > 其他分享 >AcWing 95. 费解的开关

AcWing 95. 费解的开关

时间:2022-11-06 18:11:18浏览次数:48  
标签:第一行 int 费解 turn 枚举 操作 include 95 AcWing

第一个难点:如何枚举第一行的操作(指数类型的枚举,可以使用第一题的指数型枚举)
这里使用二进制类型枚举
1 1 0 1 0 = 26
反过来任何一个整数0-65536 也可以用二进制表示
image

0-31 代表每一种方案
怎样看第i位是不是1; i>>k & 1
image

第二个难点: 如何写turn(x,y)函数
image
第三个问题: 时间复杂度

第四个问题:字符1和0互换
image

//  顺序无所谓
//  每个格子最多按一次
// 枚举第一行,第一行固定完,则第二行的操作是固定的
//  每一行开关的操作,完全被前一行的灯的亮灭状态所决定
// 如何枚举第一行的操作;

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6;     // 5*5=25   ,2^25

char g[N][N];
char backup[N][N];
int dx[5]={-1,0,1,0,0};
int dy[5]={0,1,0,-1,0};
// 
void turn(int x,int y){
  for(int i=0;i<5;i++){ // 枚举5个位置
    int a=x+dx[i];
    int b=y+dy[i];
    if(a<0 || a>=5 || b<0 || b>=5 ){  // 判断边界
      continue ;
    }
    g[a][b]^=1;  // 把字符的0变为1,把字符的1变为0; (可以使用if或者使用位运算; 0的ascall码是48)
  }
}


int main(){
  int T;
  cin>>T;
  while(T--){
    for(int i=0;i<5;i++){
      cin>>g[i];    // 读入棋盘
    }
    int res=10;   //
    for(int op=0;op<32;op++){  // 枚举所有的方案
      memcpy(backup,g,sizeof(g));  // 复制,在备份的棋盘上面做操作
      int step=0;  // 走的步数
      for(int i=0;i<5;i++){  // 最大不超过5步
        if(op>>i&1){ // 判断当前位置要不要操作
          step++;
          turn(0,i);
        }
      }
      for(int i=0;i<4; i++){  //第1行决定第0行, 一直执行到倒数第一行
        for(int j=0;j<5;j++){ // 每一列
          if(g[i][j]=='0'){  // 当前是灭的
            step++;  // 步数加1
            turn(i+1,j);  // 下一行的方格按一下 
          }
        }
      }
      
      bool dark =false;  // 判断最后一行是不是全亮
      for(int i=0;i<5;i++){
        if(g[4][i]=='0'){
          dark=true;
          break;
        }
      }
      if(!dark){ // 如果全亮
        res=min(res,step); // 取最小的步数
      }
      memcpy(g,backup,sizeof(g));
    }
    if(res>6){ // 无解返回-1
      res=-1;
    }
    cout<<res<<endl;
  }
  
  
  return 0;
}

标签:第一行,int,费解,turn,枚举,操作,include,95,AcWing
From: https://www.cnblogs.com/mengfengguang/p/16863254.html

相关文章

  • Acwing76场周赛
    题目链接这次还是只做出来两道题,前两题都挺简单的,注意第二题需要开longlong不开会wa,代码粘上来,以后可能会看吧第一题#include<iostream>#include<string>usingnam......
  • acwing 529 宝藏
    给一个图,选定一个点为起点,求一个生成树,代价和最小(跑一条长度为z的边的代价:z*d,d是起点的深度)n<=12 对于一个状态S,由S2,S-S2组成,其中S2的点深度为d+1  f[u][d][s]......
  • 时间 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......
  • 2022-11-04 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......
  • [AcWing 788]逆序对的数量
    点击查看代码#include<iostream>usingnamespacestd;constintN=100010;intn;intq[N],tmp[N];typedeflonglongLL;//最坏情况下逆序数为n*(n-1)/2结......
  • [AcWing 787]归并排序
    点击查看代码#include<iostream>usingnamespacestd;constintN=100010;intn;intq[N],tmp[N];voidmerge_sort(intq[],intl,intr){if(l>=r)......
  • [AcWing 786]第k个数
       点击查看代码#include<iostream>usingnamespacestd;constintN=100010;intn,k;intq[N];intquick_sort(intl,intr,intk){if(l==r......
  • AcWing 1208. 翻硬币
    //转换为目标状态#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=110;charstart[N];//初始状态charaim[N];//目标......
  • 【AcWing-Linux】05. Git
    Git一、Git简介Git是一个分布式版本控制工具,通常对于软件开发过程中的源代码文件进行管理。通过Git仓库来存储和管理这些文件,Git仓库分为两种:本地仓库:开发人员自己电脑......
  • 2022-11-03 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客即是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......