《算法竞赛·快冲300题》每日一题：“点灯游戏”
《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。
文章目录
- 题目描述
- 题解
- 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
【输出样例】
4
Impossible
题解
“点灯游戏”是一个经典问题，有多种解法。
如果没有限制“最少按钮数”，只要求能实现全暗或全灭，如何操作？这里介绍一种被称为“首行穷举法”的方法，简单易行。设目标是把所有的灯变黑（暗），操作如下：
（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<bits/stdc++.h>
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位设置成vif(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*nmemset(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;
}
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();}
}
Python代码
import sys
def GetBit(x, i): return (x >> i) & 1def SetBit(x, i, v):if v: x |= (1 << i)else: x &= ~(1 << i)return xdef FlipBit(x, i):x ^= (1 << i)return xdef solve(n, Map):oriLights = [0] * nfor 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 + 1for k in range(1 << n):switchs = kLights = oriLights[:]result = [0] * nfor i in range(n):result[i] = switchsfor 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] ^= switchsswitchs = Lights[i]if Lights[-1] == 0:tmp = 0for i in range(n):for j in range(n):if result[i] & (1 << j):tmp += 1ans = min(ans, tmp)return ansfor line in sys.stdin:n = int(line.strip())if n == 0: breakMap = []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)