题源AcWing[1]。提问你玩过“拉灯”游戏吗？灯排列成正方形。每个灯都有一个开关，玩家可以改变它的状态。在每一步，玩家都可以改变特定灯光的状态。当玩家改变一盏灯的状态时，会发生连锁反应：与该灯相邻的上、下、左、右灯也会相应地改变状态。我们用数字表示开着的灯，用数字表示关着的灯。以下状态10111011011111111111111111111111111111111111111年在更改左上角的光状态后：0111111100111111010011011在更改中间的光线状态后，它将变为中间，它将变为：011111111111111111111111111，给出了一些初始状态，以某些游戏为特定的一部分，以下是一些游戏，判断玩家是否可以在一个步骤内打开所有灯。输入格式的第一行输入一个正整数，表示数据中共有待解博弈的初始状态。下面几行数据被分成几组，每组数据有行，每一行有字符。每组数据描述了游戏的初始状态。每组数据由一个空行分隔。输出格式一共输出多行数据，每行有一个小于等于的整数，表示对于输入数据中对应的游戏状态，使所有灯全亮所需的最少步数。对于游戏的某个初始状态，如果不能在steps内点亮所有的灯，则输出。Datarangeinputsample:3001111110101111010111011111011101111111111111111111111111111111111111111OutputSampleSampleSample:32-1有3个重要性质。一个灯我们不需要按两次或更多次，因为按两次相当于不按，按三次相当于按两次+一次（也就是一次）。因此：因为压灯的顺序并不重要，我们可以先把第一排的灯全部压上。我们发现，把第一排要压的灯都压完后，如果想让第一排全亮，那我只能用一种方式压第二排，也就是压第二排。不亮的那一行下面的灯（下面举例）第一行的状态是10011（1表示灯亮），第二行的动作是01100（1表示按下按钮）.那么，我们如何保证第二行完全点亮呢？只有第三行才能解决！那么，我们如何保证最后一行（第五行）全亮呢？没有保证！我们发现，如果第一行是根据规律确定的，那么接下来的二、三、四、五行，以及是否可以完全点亮就是确定的。因此，对于任意一个输入状态，我们遍历第一行的所有32个方法，看看有哪些是可以全点亮的（通过检测第五行的状态），以及这些全点亮类型中是否有数量为小于等于6的操作，如果有，返回操作数，否则返回-1。代码#include#include#includeusingnamespacestd;constintN=5+5;//加5更安全//注意接收时使用字符串更方便，因为没有空格chargininputstream每一行[N][N];//记录灯的当前情况//upperrightlowerleftmiddleintdx[5]={0,1,0,-1,0};intdy[5]={1,0,-1,0,0};//根据x行y列，将自身倒置，上下左右五个灯voidturn(intx,inty){for(inti=0;i<5;++i){inta=x+dx[i],b=y+dy[i];if(0<=a&&a<5&&0<=b&&b<5)g[a][b]=g[a][b]=='1'?'0':'1';}}intwork(){intans=2e9;//第一层循环，遍历所有按下第一个的情况row//k为压缩状态，最小0b00000表示None，//最大0b11111表示全部按下//备份，因为后面的操作会改变gcharbackup[N][N];memcpy(backup,g,sizeofg);for(intk=0;k<(1<<5);++k){//确保我们的g是输入gmemcpy(g,backup,sizeofbackup);//当第一行是k时，操作总数为..intres=0;//用res记录//执行k（根据k压第一行）for(intj=0;j<5;++j){if(k>>j&1){res++;turn(0,j);}}//第一行确认，第二行确认//因为只有第二行操作得当//第一行才能完全点亮//以此类推,第二行设置后,第三行设置第二行判断for(inti=0;i<4;++i){for(intj=0;j<5;++j){if(g[i][j]=='0'){res++;turn(i+1,j);}}}//以上操作必须保证前4行全亮//但第5行不是一定全亮，第五行全亮，真的有效操作boolsuccess=true;for(intj=0;j<5;++j){if(g[4][j]=='0'){success=false;break;}}//如果是有效操作，我们看看开关被按下了多少次if(success)ans=min(res,ans);}//根据题意返回输出值if(ans>6)return-1;returnans;}intmain(){intn;cin>>n;while(n--){for(inti=0;i<5;++i)cin>>g[i];printf("%d\n",work());}}参考文献[1]AcWing:https://www.acwing.com/
