算法基础学习【1】（下）：枚举（POJ1222熄灯问题）

 原题链接：http://poj.org/problem?id=1222

/*
* POJ1222：
题解：
    思路：
    每个按钮只需按下一次
    按钮按键的顺序可以随意
    枚举第一行状态

    实现：
    观察到只有0，1，可以使用一维char类型对于灯初始状态以及灯操作存储。
    枚举第一列，可以通过2的六次方的二进制进行状态存储，位运算获取。

*/

#include 
#include <string>
#include 
#include 
using namespace std;


int Get_bit(char c, int i)
{
    return (c >> i) & 1;
}
//与操作取值,取字符c的第i个bit，也就是01矩阵中的一个元素

void Set_bit(char &c ,int i,int v)
{
    if (v)
    {
        c|= (1 << i);
        //将第i列的数据与1或运算，也即将那一行赋为1
    }
    else
    {
        c &= ~(1 << i);
        //A &= ~B是给B中为1的位对应于A的同样位上置0（单片机中的操作）
    }
}
//设置字符c第i位为v

void FlipBit(char& c, int i)
{
    c ^= (1 << i);
}
//翻转第i位的值
//异或：参加运算的两个对象，如果两个位为“异”（值不同），则该位结果为1，否则为0

void Output_result(int t, char result[])
{
    cout << "PUZZLE#" << t << endl;
    for (int i = 0; i < 5 ; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            cout << Get_bit(result[i], j);
            if (j < 5)
            {
                cout<<"  ";
            }    
        }
        cout << endl;
    }
}
//输出整个矩阵，也就是所有的按键按下的方法

int main()
{

    char g_ori_Lights[5];
    char g_lights[5];
    char g_result[5];
    char switches;
    int T;
    cin >> T;
    for (int t = 1; t < T + 1; ++t)
    {
        memset(g_ori_Lights, 0, sizeof(g_ori_Lights));
        for (int i = 0; i < 5; ++i)
        {
            for (int j = 0; j < 6; ++j)
            {
                int s;
                cin >> s;
                Set_bit(g_ori_Lights[i], j, s);
            }
        }
        //读入所有的初始开关数矩阵

        for (int n = 0; n < 64; ++n)
        {
            
            memcpy(g_lights, g_ori_Lights, sizeof(g_ori_Lights));
            switches = n;
            //ori_lights初始化g_lights

            for (int i = 0; i < 5; ++i)
            {
                //此循环处理第i行
                g_result[i] = switches;
                for (int j = 0; j < 6; j++)
                {
                    //此循环处理第i行j列开关
                    if (Get_bit(switches, j))
                    {
                        if (j > 0)
                        {
                            FlipBit(g_lights[i], j - 1);
                            //翻转j的左边一位（已经判断左边存在数字）
                        }
                        FlipBit(g_lights[i], j);
                        //翻转j
                        if (j < 5)
                        {
                            FlipBit(g_lights[i], j + 1);
                            //翻转j的右边一位（已经判断右边存在数字
                        }
                    }

                }

                if (i < 4)
                {

                    g_lights[i + 1] ^= switches;
                    /*
                       ***处理第i+1行的那一个灯的翻转***
                       switchs假设的是第一行的翻转后状态，一共有64种
                       对于第二行，应该将第一行中没有变暗的位置进行操作
                       异或操作，则与1异或（亮的灯调暗）翻转，与0异或（暗的灯不管）不会翻转
                    */

                    switches = g_lights[i];
                }
            }
        if (g_lights[4] == 0)
        {
                Output_result(t, g_result);
                break;
        }
            
        }
        
        
    
    }
    return 0;
}

草率写一下解题思路，还是有没看得特别懂的地方：

由于对于每一种数组情况枚举是不现实的，我们采用的是对第一行进行枚举，第一行枚举结果决定了第二行的结果，因为只有第二行和第一行本身才能控制第一行的灯亮与否。

同理，第三行我们也可以确定.......因此，只需对第一行一共64种情况枚举即可；

这里，因为矩阵内部全是01的，我们巧妙运用了位运算与二进制来存储数组元素；

初始化掠过，这里我们主要操作三个数组以及一个存储行的结构switches

分别对应原来数组（读写入数据）  操作数组（动态改变）  与结果数组（最后输出）

    char g_ori_Lights[5];
    char g_lights[5];
    char g_result[5];
    char switches;


写这个题主要目的是注释一下方法
对于位运算的使用，二进制存储01数组使用，以及这种枚举简化进行学习。