《算法竞赛·快冲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

【输出样例】

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)