POJ1222

学到几个新东西

• **利用位操作也许会使问题的处理变得更加方便！
• ** 异或运算符的妙用：
  
  • 1.交换两数更高效
  • 2.反转某一位（参见下面的程序中的Flip函数）

        a ^= b;
        b ^= a; 
        a ^= b;
  

 

  
1
  
2
  
3
 

#include <memory>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int GetBit(char c,int i)
{// 取c 的第i 位
    return ( c >> i ) & 1;
}
void SetBit(char & c,int i, int v)
{// 设置c 的第i 位为v
    if( v )
        c |= ( 1 << i);
    else
        c &= ~( 1 << i);
}
void Flip(char & c, int i)
{// 将c 的第i 位为取反
    c ^= ( 1 << i);
}
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()
{
    char oriLights[5]; // 最初灯矩阵，一个比特表示一盏灯
    char lights[5]; // 不停变化的灯矩阵
    char result[5]; // 结果开关矩阵
    char switchs;  // 某一行的开关状态
    int T;
    cin >> T;
    for( int t = 1; t <= T; ++ t)
    {
        memset(oriLights,0,sizeof(oriLights));
        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 )
        { // 遍历首行开关的64 种状态
            memcpy(lights,oriLights,sizeof(oriLights));
            switchs = n; // 第i 行的开关状态
            for( int i = 0;i < 5; ++i )
            {
                result[i] = switchs; // 第i 行的开关方案
                for( int j = 0; j < 6; ++j )
                {
                        if( GetBit(switchs,j))
                    {
                        if( j > 0)
                            Flip(lights[i],j-1);// 改左灯
                        Flip(lights[i],j);// 改开关位置的灯
                        if( j < 5 )
                            Flip(lights[i],j+1);// 改右灯
                    }
                }
                if( i < 4 )
                    lights[i+1] ^= switchs;// 改下一行的灯
                switchs = lights[i]; // 第i+1 行开关方案和第i 行灯情况同
            }
            if( lights[4] == 0 )
            {
                OutputResult(t,result);
                break;
            }
        } // for( int n = 0; n < 64; n ++ )
    }
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
 

“

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/60144484