枚举类型:熄灯问题(java)

简介: 枚举:在实际问题中,有些变量的取值被限定在一个有限的范围内。

描述

有一个由按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即,如果灯原来是点亮的,就会被熄灭;如果灯原来是熄灭的,则会被点亮。在矩阵角上的按钮改变3盏灯的状态;在矩阵边上的按钮改变4盏灯的状态;其他的按钮改变5盏灯的状态。
在这里插入图片描述
用X标记的按钮表示被按下,右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮,直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时,一个操作会抵消另一次操作的结果。在下图中,第2行第3、5列的按钮都被按下,因此第2行、第4列的灯的状态就不改变。
在这里插入图片描述
需要按下哪些按钮,恰好使得所有的灯都熄灭。根据上面的规则,我们知道1)第2次按下同一个按钮时,将抵消第1次按下时所产生的结果。因此,每个按钮最多只需要按下一次;2)各个按钮被按下的顺序对最终的结果没有影响;3)对第1行中每盏点亮的灯,按下第2行对应的按钮,就可以熄灭第1行的全部灯。如此重复下去,可以熄灭第1、2、3、4行的全部灯。同样,按下第1、2、3、4、5列的按钮,可以熄灭前5列的灯。

输入

5行组成,每一行包括6个数字(0或1)。相邻两个数字之间用单个空格隔开。0表示灯的初始状态是熄灭的,1表示灯的初始状态是点亮的。

输出

5行组成,每一行包括6个数字(0或1)。相邻两个数字之间用单个空格隔开。其中的1表示需要把对应的按钮按下,0则表示不需要按对应的按钮。

样例输入

0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0

样例输出

1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0

问题来源:http://bailian.openjudge.cn/practice/2811/

解题分析

来源:北大郭炜老师

• 第2次按下同一个按钮时,将抵消第1次按下时所产生的结果,所以每个按钮最多只需要按下一次
• 各个按钮被按下的顺序对最终的结果没有影响
• 对第1行中每盏点亮的灯, 按下第2行对应的按钮, 就可以熄灭第1行的全部灯
• 如此重复下去, 可以熄灭第1, 2, 3, 4行的全部灯

第一想法:

枚举所有可能的按钮(开关)状态, 对每个状态,计算一下最后灯的情况, 看是否都熄灭。 每个按钮有两种状态(按下或不按下),一共有30个开关,
那么状态数是230, 太多, 会超时 。

如何减少枚举的状态数目呢?

基本思路: 如果存在某个局部, 一旦这个局部的状态被确定, 那么剩余其他部分的状态只能是确定的一种, 或者不多的n种,
那么就只需枚举这个局部的状态即可。

本题是否存在这样的 “ 局部” 呢?

经过观察, 发现第1行就是这样的一个 “ 局部”

因为第1行的各开关操作方案确定的情况下, 这些开关操作过后,将导致第1行某些灯是亮的, 某些灯是灭的。

要熄灭第1行某个亮着的灯(假设位于第i列), 那么唯一的办法就是按下第2行第i列的开关。(因为第1行的开关已经用过了,

而第3行及其后的开关不会影响到第1行) 为了使第1行的灯全部熄灭, 第2行的合理开关操作方案就是唯一的 。

第2行的开关操作过后,为了熄灭第2行的灯, 第3行的合理开关操作方案就也是唯一的。以此类推, 最后一行的开关操作方案也是唯一的。
只要第1行的操作方案定下来, 记作A, 那么剩余行的操作方案就是确定唯一的了 。

推算出最后一行的开关操作方案, 然后看看最后一行的开关操作过后,最后一行的所有灯是否都熄灭: 如果是, 那么A就是一个解的状态; 如果不是,
那么A不是解的状态, 第1行换个状态重新试试。

只需枚举第1行的操作方案, 状态数是2^6 = 64

代码实现:

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int[][] lights = new int[5 + 2][6 + 2];
    static int[][] lightsStates = new int[5 + 2][6 + 2];
    static int[][] btnStates = new int[5 + 2][6 + 2];

    static int index = 0;
    static int[][] meiJu = new int[64][6];
    static int[] cur = new int[6];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 1; i <= 5; ++i) {
            for (int j = 1; j <= 6; ++j) {
                lights[i][j] = sc.nextInt();
                lightsStates[i][j] = lights[i][j];
            }
        }

        bfs(0);

        for (int i = 0; i < 64; ++i) {

            //按下第一行按钮后灯的状态
            pressLine(meiJu[i]);
            //根据按后,第一行的状态更新整个数据的状态
            updateArray();

            //检查灯是否已经全部熄灭了
            if (!checkCurLightsStates()) {
                //如果灯没有全部熄灭 ,就把所有状态更新为原来的
                for (int l = 1; l <= 5; ++l) {
                    lightsStates[l] = Arrays.copyOf(lights[l], 6 + 2);
                }
                btnStates = new int[5 + 2][6 + 2];
            } else {
                break;
            }


        }

        for (int i = 1; i <= 5; ++i) {
            for (int j = 1; j <= 6; ++j) {
                if (j != 6) System.out.print(btnStates[i][j] + " ");
                else System.out.print(btnStates[i][j]);
            }
            if (i != 5) System.out.println();
        }

    }

    public static boolean checkCurLightsStates() {
        for (int i = 1; i <= 5; ++i) {
            for (int j = 1; j <= 6; ++j) {
                if (lightsStates[i][j] == 1) {
                    return false;
                }
            }
        }
        return true;
    }


    public static void pressLine(int[] press) {
        for (int i = 0; i < press.length; ++i) {
            if (press[i] == 1) pressBtn(1, i + 1);
        }
    }


    //某个按钮被按下后,状态改变
    public static void pressBtn(int x, int y) {
        lightsStates[x][y] = 1 ^ lightsStates[x][y];
        lightsStates[x][y - 1] = 1 ^ lightsStates[x][y - 1];
        lightsStates[x][y + 1] = 1 ^ lightsStates[x][y + 1];
        lightsStates[x - 1][y] = 1 ^ lightsStates[x - 1][y];
        lightsStates[x + 1][y] = 1 ^ lightsStates[x + 1][y];
        btnStates[x][y] = 1;
    }


    //根据第一行更新整个数组
    public static void updateArray() {

        for (int i = 2; i <= 5; ++i) {
            for (int j = 1; j <= 6; ++j) {
                if (lightsStates[i - 1][j] == 1) {
                    pressBtn(i, j);
                }
            }
        }
    }


    //查询出所有的组合情况一共64种
    public static void bfs(int n) {
        if (n >= 6) {
            meiJu[index++] = Arrays.copyOf(cur, 6);
            return;
        }
        for (int i = 0; i < 2; ++i) {
            cur[n] = i;
            bfs(n + 1);
            cur[n] = 0;
        }
    }
}
目录
相关文章
|
编解码 Android开发
Android native层实现MediaCodec编码H264/HEVC
Android平台在上层实现mediacodec的编码,资料泛滥,已经不再是难事,今天给大家介绍下,如何在Android native层实现MediaCodec编码H264/HEVC,网上千篇一律的接口说明,这里不再赘述,本文主要介绍下,一些需要注意的点,权当抛砖引玉,相关设计界面如下:
437 0
|
Java Android开发
jvisualvm分析jvm内存溢出
jvisualvm分析jvm内存溢出
1438 0
jvisualvm分析jvm内存溢出
|
机器学习/深度学习 存储 人工智能
人工智能在现代软件开发中的变革与挑战
在当今的技术领域,人工智能(AI)已成为推动软件开发革新的核心力量。本文探讨了AI在软件开发中的应用,包括自动化代码生成、智能测试和维护,以及面临的挑战,如数据隐私和伦理问题,旨在为开发者提供全面的视角。
507 0
|
SQL 关系型数据库 MySQL
mysql密码错误-ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using passwor:yes)
这篇文章提供了解决MySQL数据库"Access denied for user 'root'@'localhost' (using password: YES)"错误的方法,通过跳过密码验证、修改root密码,然后重启服务来解决登录问题。
mysql密码错误-ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using passwor:yes)
|
安全 关系型数据库 MySQL
解决:'mysql' 不是内部或外部命令,也不是可运行的程序或批处理文件。 (MySQL环境变量的配置)
解决:'mysql' 不是内部或外部命令,也不是可运行的程序或批处理文件。 (MySQL环境变量的配置)
4428 0
解决:'mysql' 不是内部或外部命令,也不是可运行的程序或批处理文件。 (MySQL环境变量的配置)
|
算法 Java
算法-称硬币(枚举-java)
算法-称硬币(枚举-java)
|
机器学习/深度学习 算法 程序员
面试题|关于“递归”一篇文章就够了
面试题|关于“递归”一篇文章就够了
374 0
面试题|关于“递归”一篇文章就够了
|
6天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1143 3
|
5天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
728 11