《算法竞赛·快冲300题》每日一题：“点灯游戏”

《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。

“ 点灯游戏” ，链接： http://oj.ecustacm.cn/problem.php?id=1134

题目描述

【题目描述】 有一个n*n的灯泡矩阵，b表示灯暗，w表示灯亮。每个灯的位置上都有控制着这盏灯的按钮。当按下一个按钮后，该按钮以及周围位置(上下左右)的灯都会改变状态（亮->暗，暗->亮）。最少按下多少个按钮可以使得所有的灯都亮或者都暗。
【输入格式】 输入有多组数据，每组数据第一行有一个整数n（1≤n≤10），接下来n行，每行n个字符表示初始的灯泡矩阵。
【输出格式】 如果可以使得所有的灯泡都亮或者都暗，输出最少按下的按钮数目。如果无法达到，输出"Impossible"(不含引号) 。
【输入样例】

4
bwwb
bbwb
bwwb
bwww
4
bwbw
wwww
bbwb
bwwb
1
2
3
4
5
6
7
8
9
10

【输出样例】

4
Impossible
1
2

---

题解

   “点灯游戏”是一个经典问题，有多种解法。
  如果没有限制“最少按钮数”，只要求能实现全暗或全灭，如何操作？这里介绍一种被称为“首行穷举法”的方法，简单易行。设目标是把所有的灯变黑（暗），操作如下：
  （1）第一行不按动按钮，只需找到白灯的位置；
  （2）第二行对应第一行的白灯的位置，都是按钮，按下后，它上下左右的灯都变色，特别是上一行的白灯都会变黑，从而保证第一行都变成黑色；
  （3）每一行的按钮，都对应上一行的白灯，使上一行全变黑。
  本题要求得“最少按钮数”，可以把所有按钮都试一遍，找到最少的那种。为了减少尝试的次数，可以结合上述方法。本题的n≤10，规模很小，这种暴力法也可行。
  假设目标是最后都变成黑色，从第一行开始，逐行按动按钮。
  第一行有0000~1111共16种按按钮的方法。0000表示1个都不按，0001表示只按第1个按钮，0010表示只按第2个按钮，0011表示按第1、第2个按钮，…，等等。
  第一行选择一种方法按完之后，继续按动第二行。第二行如何按？显然要保证第一行都变成黑色才行。那么应该让第二行的按钮位置跟第一行的白色位置一样，因为第二行的按钮按动之后，它上面的白色会跟着变成黑色。
  按上述规则继续按后面的行，直到结束。
  下面举例说明。图中的“初态”是第一个样例的灯，黑表示暗，白表示亮。左上角坐标(0,0)，右下角坐标(3,3)。

  （1）第一行的按钮设置。以第一行按0011为例，就是按第1、2个按钮。按第1个按钮(0,0)后得到图(1)，再按第2个按钮(0,1)后得到图(2)。记录两个按钮的坐标(0,0)、(0,1)。
  （2）第二行的按钮设置。此时第一行只有第2个灯是白的，需要变成黑色。那么第二行必须按第2个按钮，才能让上面的白灯变成黑灯。第二行需要按的按钮的坐标是(1,1)，得到图(3)的结果，第一行全黑了。
  （3）第三行的按钮设置。由于第二行全是黑的，所以第三行不用按了。
  （4）第四行的按钮设置。第三行的第3个灯是白的，需要变成黑色。那么第四行必须按第3个按钮，才能让上面的白灯变成黑灯。得到图(4)的结果，第三行全黑了。第四行需要按的按钮坐标是(3,2)。
  这四行结束后，第四行也变成了全黑，说明这是一次成功的操作，共按了4个按钮。
  第一行共有16种按钮设置方法，都按以上步骤操作一遍，其中按动按钮最少的就是结果全是黑灯的答案。
  以上假设最后都是黑色，也可以假设最后都是白色，再操作一次即可。取最少的按钮次数就是本题的答案。
  请读者按这个思路编码。下面的代码供参考。
【重点】 思维 。

C++代码

#include
using namespace std;
char Map[11][11];
int n;
int GetBit(int x, int i){             //取出x的第i位
    return (x >> i) & 1;
}
void SetBit(int &x, int i, int v){        //将x的第i位设置成v
    if(v)  x |= (1 << i);
    else   x &= ~(1 << i);
}
void FlipBit(int &x, int i){         //将x的第i位取反
    x ^= (1 << i);
}
int solve(){
    int oriLights[11];    //灯的初态
    int Lights[11];       //按动按钮之后的灯的新状态
    int result[11];       //存需要按动的按钮
    int ans = n * n + 1;  //需要按动的按钮数不会大于n*n
    memset(oriLights, 0, sizeof(oriLights));
    for(int i = 0; i < n; i++)           //把灯用二进制的位来表示，第i行，第j列
        for(int j = 0; j < n; j++){
            if(Map[i][j] == 'b')  SetBit(oriLights[i], j, 0);   //0表示暗
            else                  SetBit(oriLights[i], j, 1);   //1表示亮
        }
    for(int k = 0; k < (1<<n); k++)  {        //k是第0行的按钮，有0000~1111种按钮设置
        memcpy(Lights, oriLights, sizeof(oriLights)); 
        int switchs = k;                      //第0行的按钮，例如k=0011，就是按第1、2个按钮
        for(int i = 0; i < n; i++) {          //逐一处理每行的灯
            result[i] = switchs;              //用result[i]记录第i行的按钮
            for(int j = 0; j < n; j++) {      //逐一处理每一列的灯
                if(GetBit(switchs, j)) {   
                    if(j > 0)    FlipBit(Lights[i], j-1);  //j前面的第j-1灯变色
                    FlipBit(Lights[i], j);                     //第j个灯变色
                    if(j < n-1)  FlipBit(Lights[i], j+1);  //j后面的第j+1灯变色
                }
            }
            if(i < n-1)   Lights[i+1] ^= switchs;      //修改下一行的灯
            switchs = Lights[i];            //第i+1行按钮位置和第i行灯的位置相同
        }
        if(Lights[n-1] == 0) {            //最后一行也全变黑了，成功
            int tmp = 0;                    //tmp为开关矩阵中1的数目
            for(int i = 0; i < n; i++)      //(i,j)就是需要按动的按钮坐标
                for(int j = 0; j < n; j++)
                    if(result[i] & (1<<j))
                        tmp++;
            ans = min(ans, tmp);
        }
    }
    return ans;
}
int main(){
    while(scanf("%d", &n) != EOF)  {
        memset(Map, 0, sizeof(Map));
        for(int i = 0; i < n; i++)  scanf("%s", Map[i]);
        int ans = solve();                  //以全黑为目标做一次
        for(int i = 0; i < n; i++)          //反过来以全白为目标做一次
            for(int j = 0; j < n; j++)
                if(Map[i][j] == 'b')  Map[i][j] = 'w';
                else                  Map[i][j] = 'b';
        ans = min(ans, solve());
        if(ans > n * n)  puts("Impossible");
        else             printf("%d\n", ans);
    }
    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

Java代码

import java.util.*;  
public class Main {  
    static int GetBit(int x, int i) {
        return (x >> i) & 1;
    }  
    static int SetBit(int x, int i, int v) {
        if (v == 1)   x |= (1 << i);
        else             x &= ~(1 << i);
        return x;
    }  
    static int FlipBit(int x, int i) {
        x ^= (1 << i);
        return x;
    }  
    static int solve(int n, String[] Map) {
        int[] oriLights = new int[n];
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) {
                if (Map[i].charAt(j) == 'b')  oriLights[i] &= ~(1 << j);
                else        oriLights[i] |= (1 << j);
            }
        int ans = n * n + 1;
        for (int k = 0; k < (1 << n); k++) {
            int switchs = k;
            int[] Lights = oriLights.clone();
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = switchs;
                for (int j = 0; j < n; j++) {
                    if (GetBit(switchs, j) == 1) {
                        if (j > 0)   Lights[i] = FlipBit(Lights[i], j-1);
                        Lights[i] = FlipBit(Lights[i], j);
                        if (j < n-1) Lights[i] = FlipBit(Lights[i], j+1);
                    }
                }
                if (i < n-1)      Lights[i+1] ^= switchs;
                switchs = Lights[i];
            }
            if (Lights[n-1] == 0) {
                int tmp = 0;
                for (int i = 0; i < n; i++) 
                    for (int j = 0; j < n; j++) 
                        if ((result[i] & (1 << j)) != 0) 
                            tmp++;
                ans = Math.min(ans, tmp);
            }
        }
        if (ans > n * n)     return -1;
        else             return ans;

    }
  
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n == 0)  break; 
            String[] Map = new String[n];
            for (int i = 0; i < n; i++)  Map[i] = scanner.next();
             int ans = solve(n, Map);
            // 循环遍历数组并替换字符
            for (int i = 0; i < n; i++) {
                Map[i] = Map[i].replace('b', 'x');  // 将'b'替换为临时字符'x'
                Map[i] = Map[i].replace('w', 'b');  // 将'w'替换为'b'
                Map[i] = Map[i].replace('x', 'w');  // 将临时字符'x'替换为'w'
            }
            ans = Math.min(ans, solve(n, Map));
            if (ans == -1)   System.out.println("Impossible");
            else             System.out.println(ans);
        }
        scanner.close();
    }
}
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

Python代码

  

 import sys
def GetBit(x, i):   return (x >> i) & 1
 
def SetBit(x, i, v):
    if v:     x |= (1 << i)
    else:     x &= ~(1 << i)
    return x
 
def FlipBit(x, i):
    x ^= (1 << i)
    return x
 
def solve(n, Map):
    oriLights = [0] * n
    for i in range(n):
        for j in range(n):
            if Map[i][j] == 'b':  oriLights[i]=SetBit(oriLights[i], j, 0) 
            else:                 oriLights[i]=SetBit(oriLights[i], j, 1) 
    ans = n * n + 1
    for k in range(1 << n):
        switchs = k
        Lights = oriLights[:]
        result = [0] * n
        for i in range(n):
            result[i] = switchs
            for j in range(n):
                if GetBit(switchs, j):
                    if j > 0:   Lights[i] = FlipBit(Lights[i], j-1)
                    Lights[i] = FlipBit(Lights[i], j)
                    if j < n-1: Lights[i] = FlipBit(Lights[i], j+1)
            if i < n-1:   Lights[i+1] ^= switchs
            switchs = Lights[i]
        if Lights[-1] == 0:
            tmp = 0
            for i in range(n):
                for j in range(n):
                    if result[i] & (1 << j):
                        tmp += 1
            ans = min(ans, tmp)
    return ans
 
for line in sys.stdin:
    n = int(line.strip())
    if n == 0:  break
    Map = []
    for i in range(n):   Map.append(input().strip())
    ans = solve(n, Map)
    F = {}
    F['b'] = 'w'
    F['w'] = 'b'
    for i in range(n):
        Map[i] = ''.join([F[x] for x in Map[i]])
         
    ans = min(ans,solve(n, Map))
    if ans > n * n:     print("Impossible")
    else:               print(ans)

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