C++基础算法学习——熄灯问题

有一个由按钮组成的矩阵, 其中每行有6个按钮, 共5行
– 每个按钮的位置上有一盏灯
– 当按下一个按钮后, 该按钮以及周围位置(上边, 下边,
左边, 右边)的灯都会改变状态
26熄灯问题 POJ1222
– 如果灯原来是点亮的, 就会被熄灭
– 如果灯原来是熄灭的, 则会被点亮
• 在矩阵角上的按钮改变3盏灯的状态
• 在矩阵边上的按钮改变4盏灯的状态
• 其他的按钮改变5盏灯的状态
27熄灯问题 POJ1222
 与一盏灯毗邻的多个按钮被按下时,一个操作会抵消另一次操
作的结果
 给定矩阵中每盏灯的初始状态,求一种按按钮方案,使得所有
的灯都熄灭熄灯问题 POJ1222
 输入:
– 第一行是一个正整数N, 表示需要解决的案例数
– 每个案例由5行组成, 每一行包括6个数字
– 这些数字以空格隔开, 可以是0或1
– 0 表示灯的初始状态是熄灭的
– 1 表示灯的初始状态是点亮的
29熄灯问题 POJ1222
 输出:
– 对每个案例, 首先输出一行,
输出字符串 “PUZZLE #m”, 其中m是该案例的序号
– 接着按照该案例的输入格式输出5行
• 1 表示需要把对应的按钮按下
• 0 表示不需要按对应的按钮
• 每个数字以一个空格隔开

代码如下：

#include <iostream>

#include<string.h>

using namespace std;

char Oright[];

char Light[];

char Result[];

void SetChar(char &  t,int j,int s);

void OutPut(char * t);

int GetChar(char  t,int j);

void Flip(char & s,int i);

int main()

{

    int switches;

    for(int i=;i<;i++)//一个位一个位的存储。

    {

        for(int j=;j<;j++)

        {

            int s;

            cin>>s;

            SetChar(Oright[i],j,s);

        }

    }

    for(int i=;i<;i++)

    {

        memcpy(Light,Oright,sizeof(Oright));

        switches=i;

        for(int j=;j<;j++)//对于i的值，每行开始测试

        {

            Result[j]=switches;//Result存储的是开关的按压方案。

            for(int k=;k<;k++)//每列开始测试

            {

                if(GetChar(switches,k))

                {

                    if(k>)

                        Flip(Light[j],k-);//左边开始变化

                    Flip(Light[j],k);

                    if(k<)

                        Flip(Light[j],k+);//右边开始变化

                }

            }

            if(j<)

                Light[j+]^=switches;

            switches=Light[j];

        }

        if(Light[]==)

        {

            cout<<"结束！"<<endl;

            OutPut(Result);

            break;

        }

    }

    return ;

}

void Flip(char & s,int i)

{

    s=s^(<<i);

}

int GetChar(char  t,int j)

{

    return (t>>j)&;

}

void SetChar(char & t,int j,int s)

{

    if(s==)

        t=t|(<<j);

    else

         t=t&(~(<<j));

}

void OutPut(char * t)

{

    for(int i=;i<;i++)

    {

        for(int j=;j<;j++)

        {

            cout<<GetChar(t[i],j);

            cout<<"   ";

        }

        cout<<endl;

    }

}