美文网首页
5乘6方格的熄灯问题

5乘6方格的熄灯问题

作者: Tangbh | 来源:发表于2017-03-13 20:53 被阅读23次

以下是代码

#include<iostream>
#include<memory>
#include<string>
#include<cstring>
using namespace std;
//一个矩阵,一个点表示一盏灯,当按下这个按钮后这个点包括与其相邻的点的状态会被改变。
//输入一个矩阵表示现在的状态。
//输出一个矩阵表示要如何按按钮才能将灯全部熄灭


//全部枚举的话可能性太多,会超时,可以采用枚举局部的方法,当有个局部确定的时候,其他部分就只有一种或者n钟可能的情况
//第一行就是一个局部
//要熄灭第一行第i列的灯,唯一的办法就是按下第二行,第i列的开关(第三行及其后的开关不会影响到第1行
//以此类推,当一行的状态确定时,下一行的按法也是确定的
//如果最后一行的

char oriLights[5];
char Lights[5];
char Result[5];

int GetBit(char c, int i)        //获取第i位的状态
{
    return (c >> i) & 1;

}

void SetBit(char &c, int i, int v)       //设置第i位的状态
{
    if (v)
    {
        c |= (1 << i);  //第i位设置为1,按位或运算
    }
    else {
        c &= ~(1 << i);     //第i位设置为1 ,然后取反,按位与运算
    }
}

void FlipBit(char &c, int i)     //改变第i位的状态
{
    c ^= (i << i);    //与1异或运算相当于取反
}

void OutputResult(int t, char result[])    //输出数组
{
    cout << "PUZZLE #" << t << endl;
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cout << GetBit(result[i], j);
            if (j < 5) {
                cout << " ";
            }
        }
        cout << endl;
    }
}

int main()
{
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++)
    {
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                int s;
                cin >> s;
                SetBit(oriLights[i],j, s);    //设置现在灯的状态的的矩阵
                
            }
            
        }
        for (int n = 0; n < 64; n++)
        {
            int switchs = n;          //n对应的二进制表示按按钮的方法
            for (int i = 0; i < 5; i++)
            {
                Result[i] = switchs;              
                for (int j = 0; j < 6; j++)          //一行六列,循环六次
                {
                    if (GetBit(switchs, j))      //获取第j列的值
                    {
                        if (j > 0)
                        {
                            FlipBit(Lights[i], j-1);
                        }
                        FlipBit(Lights[i], j);
                        if (j < 5)
                        {
                            FlipBit(Lights[i], j + 1);
                        }
                        switchs = Lights[i];
                    }
                }
                if (i < 4)     //不是最后一行的话,也要改变下一行的状态
                {
                    Lights[i + 1] ^= switchs;         //取反
                }

            }
            if (Lights[4] == 0)   //判断按法是否符合预期结果
            {
                OutputResult(t, Result);     //输出矩阵
                break;
            }

        }

    }

}

相关文章

  • 5乘6方格的熄灯问题

    以下是代码

  • 算法入门(5)熄灯问题

    参考该链接和B站上的视频做一些简单的拓展。题目描述:有一个5行6列的按钮矩阵,矩阵中每一个位置都有一个灯和一个按钮...

  • 熄灯问题

  • 熄灯问题

    1.有一个由按钮组成的矩阵, 其中每行有6个按钮, 共5行2.每个按钮的位置上有一盏灯3.当按下一个按钮后, 该按...

  • 熄灯问题

  • 7月。 4539

    7.1. 6包乘27 7.2 6包乘27 7.3. 4包乘27 7.4. 5包乘27. 6包乘22 7.5. 7包...

  • 11月 4292

    11.1 3包乘27 11.2 6包乘27 11.3 5包乘27 11.4 12包乘27 11.5...

  • 4月。 5935

    4.1. 9包乘27 4.2. 6包乘27. 1包乘37 4.3. 5包乘27 4.4. 8包乘27 4.5....

  • 枚举之熄灯问题

    问题描述 输入 输出 样例 解题分析 有没有状态数更少的做法? 具体实现 实现方案 程序实现 按行枚举 按列枚举 ...

  • 0030-熄灯问题

    问题描述 有一个由按钮组成的矩阵, 其中每行有 6 个按钮, 共5 行。每个按钮的位置上有一盏灯。当按下一个按钮后...

网友评论

      本文标题:5乘6方格的熄灯问题

      本文链接:https://www.haomeiwen.com/subject/whvqnttx.html