枚举算法案例--熄灯问题

硅谷探秘者 5284 0 0

熄灯问题

1.问题描述


有一个有按钮组成的矩阵,其中每行有6个按钮,共5行。

每个按钮的位置上有一盏灯。

当按下一个按钮后,该按钮以及周围位置(上下左右)的灯都会改变一次。即(原来亮的变暗,原来暗的变亮)

对矩阵中的每一盏灯设置一个初始状态。

请你写一个程序,确定需要按下那些按钮,插好使得所有的灯都被熄灭。


例图1:

QQ截图20190414165759.png

例图2:

QQ截图20190414165818.png

叉号代表按下的按钮


输入:

第一行是一个正整数n表示需要解决的案例数。

每一个案例由5行组成,每一行包括6个数字

这些数字以空格隔开,可以是0或1,0表示初始状态时熄灭的,1表示初始状态是点亮的。


输出:

对于每个案例都先输出一行“case#m”,m是案例序号

接着按照该案例的输入格式输出5行,

1表示需要把对应的按钮按下,

0表示不需要按对应的按钮。


2.算法实现(c语言实现):

#include <stdio.h>
int puzzle[6][8],press[6][8];
int guess(){
       int c,r;
       for(r=1;r<5;r++){
              for(c=1;c<7;c++){
                     press[r+1][c]=(puzzle[r][c]+press[r][c]+
                            press[r-1][c]+press[r][c-1]+press[r][c+1])%2;
              }
       }
       for(c=1;c<7;c++){
              if((press[5][c-1]+press[5][c]+press[5][c+1]+
                     press[4][c])%2!=puzzle[5][c]){
                     return 0;
              }
       }
       return 1;
}
 
void enumerate(){
       int c;
       for(c=0;c<7;c++){
              press[1][c]=0;
       }
       while(guess()==0){
              press[1][1]++;
              c=1;
              while(press[1][c]>1){
                     press[1][c]=0;
                     c++;
                     press[1][c]++;
              }
       }
       return;
}
 
int main(){
       int cases,i,r,c;
       scanf("%d",&cases);
       for(r=0;r<6;r++){
              press[r][0]=press[r][7]=0;
       }
       for(c=1;c<7;c++){
              press[0][c]=0;
       }
       for(i=0;i<cases;i++){
              for(r=1;r<6;r++){
                     for(c=1;c<7;c++){
                            scanf("%d",&puzzle[r][c]);
                     }
              }
              enumerate();
              printf("case%d\n",i+1);
              for(r=1;r<6;r++){
                     for(c=1;c<7;c++){
                            printf("%d",press[r][c]);
                     }
                     printf("\n");
              }
       }
       return 0;
}


QQ截图20190414164932.png

3.算法思路:

以第一行作为一个局部;

当第一行的按钮全部作用完以后,第一行可能还会存在部分按钮是亮的

那么要想熄灭第一行第i列的灯,必须按下第二行第i列的灯,类似的,要想熄灭第n行第i列的灯,就需要按下第n+1行,第i列的灯,直到第5行。


其含义是,要想让第一行的灯全部熄灭,那么后面的所有行的灯按下的情况就已经确定。如果作用完最后一行,发现,最后一行的灯也全部熄灭,那么按下的过程就是一个解。


猜你喜欢
数据结构与算法 11623 (returnnewint[]={1,2}),如果没有返回-1(returnnewint[]={-1,-1})。:用查找表解决实现:packageclub.test;importjava.util.HashMap;im
数据结构与算法 6012 描述:渗透,给一个n*m的矩阵,0为空白,1为白纸,2为墨水,墨水每经过每一秒会将上下左右相邻的白纸染成黑色,然后继续渗透,判断此图中的白纸最终是否能够全部被墨水染上色,若能需要输出所有白纸
数据结构与算法 6499 八皇后,是一个古老而著名的,是回溯的典型。该是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行
数据结构与算法 5910 目描述思路:,只需要前两个数,满足条件的第三个数自然是2019减去前两个数。代码packagelanqiao;publicclassTestMain1
数据结构与算法 8290 描述思路:典型的广度优先搜索,根据字典序大小,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点优先先往下走,然后向左走,然后向右走,然后向上走。则最后首先到达出口的一条路径就是符合
weblog 9274 )。虽然它不返回路径本身的细节,但是可以通过对的简单修改来重建路径。该的版本也可用于查找关系R的传递闭包,或(与Schulze投票系统相关)在加权图中所有顶点对之间的最宽路径。如有一个图(可以
数据结构与算法 622 java使用欧几里得的方 publicstaticvoidmain(String[]args){ System.out.println(bili(2,6
数据结构与算法 5379 01背包是动态规划的一个经典目: 在n种物品中选取若干件(每种物品只有一件只能选择一次) 放在空间为W的背包里,每种物品的体积为wigth[1],wigth[2],wigth[3
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived
目录
祝愿神州十三飞行乘组平安归来