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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

有一个由按钮组成的矩阵, 其中每行有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[5];
char Light[5];
char Result[5];
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=0;i<5;i++)//一个位一个位的存储。
    {
        for(int j=0;j<6;j++)
        {
            int s;
            cin>>s;
            SetChar(Oright[i],j,s);
        }
    }
    for(int i=0;i<64;i++)
    {
        memcpy(Light,Oright,sizeof(Oright));
        switches=i;
        for(int j=0;j<5;j++)//对于i的值，每行开始测试
        {
            Result[j]=switches;//Result存储的是开关的按压方案。
            for(int k=0;k<6;k++)//每列开始测试
            {
                if(GetChar(switches,k))
                {
                    if(k>0)
                        Flip(Light[j],k-1);//左边开始变化
                    Flip(Light[j],k);
                    if(k<5)
                        Flip(Light[j],k+1);//右边开始变化
                }
            }
            if(j<4)
                Light[j+1]^=switches;
            switches=Light[j];
        }
        if(Light[4]==0)
        {
            cout<<"结束！"<<endl;
            OutPut(Result);
            break;
        }
    }
    return 0;
}
void Flip(char & s,int i)
{
    s=s^(1<<i);
}
int GetChar(char  t,int j)
{
    return (t>>j)&1;
}
void SetChar(char & t,int j,int s)
{
    if(s==1)
        t=t|(1<<j);
    else
         t=t&(~(1<<j));
}
void OutPut(char * t)
{
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<6;j++)
        {
            cout<<GetChar(t[i],j);
            cout<<"   ";
        }
        cout<<endl;
    }
}