算法疑难杂症

枚举和找规律

字数统计: 1.2k字   |   阅读时长: 5分
, , , ,

摘要: 综合题：枚举+找规律

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个模拟的综合题，涉及到找规律、枚举、位运算等算法点。

题目

95. 费解的开关

25 盏灯排成一个 5 * 5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

例如

下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

1
2
3
4
5
6
7
8
9
10
11
12
输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。

输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。

数据范围
0<n<=500

输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：
3
2
-1

算法: 找规律 + 枚举

本题的难点在于要在上述规则的 01 矩阵点击游戏中，找到以下 3 个性质

  1. 每个位置至多点击一次
  2. 若固定第一行(不能再点击第一行)，则满足题意的点击方案至多有一种，因为第 i 行第 j 位为 1 时，则必须点击第 i + 1 行的第 j 位才能使第 i 行第 j 位变为 0。
  3. 点击的顺序不影响最终结果

因此考虑第一行所有可能的点击结果，共 $2^{5}=32$ 种，此后从第一行开始向下递推，从第 i 行向第 i + 1 行递推时，第 i + 1 行采取的行动必须使得第 i + 1 行动完成后第 i 行均为 0。

到达第 n 行时，如果第 n 行不全为 1，则说明对应的第一行的行动方案不合法。

对第一行枚举的方法，可以参考 枚举 中的代码模板。

1
2
3
4
for(int s = 0; s < (1 << 5); ++s)
{
    ...
}

代码(C++)

虽然算法不难，但是实际上代码调试了很久。

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
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>

using namespace std;

const int N = 5;

int operate(vector<int>& board, const int i, const int s)
{
    // 按照 s 操作 board 的第 i 行
    for(int j = 0; j < N; ++j)
    {
        if(s >> j & 1)
        {
            // 按下 board[i] >> j
            board[i] ^= (1 << j);
            if(j > 0)
                board[i] ^= (1 << (j - 1));
            if(j < N - 1)
                board[i] ^= (1 << (j + 1));
            if(i > 0)
                board[i - 1] ^= (1 << j);
            if(i < N - 1)
                board[i + 1] ^= (1 << j);
        }
    }
}

int get1(int x)
{
    // x 的二进制中 1 的个数
    int n = 0;
    while(x > 0)
    {
        if(x & 1)
            ++n;
        x >>= 1;
    }
    return n;
}

int solve(vector<int> board, const int s)
{
    // 棋盘初始状态为 board, 第一行行动为 s，返回变为全 1 所需次数，不可行返回 -1
    int ans = get1(s);
    operate(board, 0, s);
    for(int i = 1; i < 5; ++i)
    {
        // 操作 board 的第 i 行，使得第 i - 1 行为 0
        int t = 0;
        for(int j = 0; j < N; ++j)
        {
            if((board[i - 1] >> j & 1) == 0)
                t |= (1 << j);
        }
        ans += get1(t);
        operate(board, i, t);
    }
    if(board[N - 1] != (1 << N) - 1)
        return -1;
    if(ans <= 6)
        return ans;
    else
        return -1;
}

int main()
{
    int n;
    cin >> n;
    vector<int> board(N);
    for(int k = 0; k < n; ++k)
    {
        board.assign(N, 0);
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
            {
                char ch;
                cin >> ch;
                board[i] |= ((ch - '0') << j);
            }
        int ans = -1;
        for(int s = 0; s < (1 << N); ++s)
        {
            // 第一行操作为 s
            int x = solve(board, s);
            if(x != -1 && x <= 6)
            {
                ans = x;
                break;
            }
        }
        cout << ans << endl;
    }
}
Share