【位运算, 递推】费解的开关

题目

95. 费解的开关 - AcWing题库

---

你玩过“拉灯”游戏吗？

$25$ 盏灯排成一个 $5 \times 5$ 的方形。

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

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

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

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

下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

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

输入格式

第一行输入正整数 $n$ ，代表数据中共有 $n$ 个待解决的游戏初始状态。

以下若干行数据分为 $n$ 组，每组数据有 $5$ 行，每行 $5$ 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 $n$ 行数据，每行有一个小于等于 $6$ 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 $6$ 步以内无法使所有灯变亮，则输出 $-1$ 。

数据范围

$0 < n \le 500$

输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

3
2
-1

解题

方法一：递推 位运算

思路

枚举第一行 $5$ 个灯所有可能的 $32$ 种状态（$00000 \sim 11111$），然后内层遍历第 $2 \sim 5$ 行每一列第开关状态，递推出是否需要改变开关的状态，具体来说：枚举到灯 $(i, j)$ 时，它上一行的灯 $(i-1, j)$ 的状态只有此时有机会被更改^[1]，如果 $(i-1, j)$ 为关灯状态，那么就要更改 $(i, j)$ 的状态并增加计数。枚举完后检查最后一层的灯是否全亮，如果全亮则说明本次枚举得到了一个合法解，尝试更新最小合法解；否则直接进入下一次枚举。

详细解法见y总的视频讲解。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 5;
    static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static boolean[][] g = new boolean[N][N];
    
    static void turn(int x, int y) {
        g[x][y] = !g[x][y];
        for (int[] DIR : DIRS) {
            int nx = x + DIR[0], ny = y + DIR[1];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N) g[nx][ny] = !g[nx][ny];
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken();
        int t = (int) in.nval;
        while (t-- > 0) {
            boolean[][] bak = new boolean[N][N];
            for (int i = 0; i < N; ++i) {
                String tmp = br.readLine();
                for (int j = 0; j < N; ++j) bak[i][j] = tmp.charAt(j) == '1';
            }
            br.readLine();
            int ans = 7;
            outer: for (int i = 0; i < 1 << N; ++i) {
                for (int j = 0; j < N; ++j) g[j] = bak[j].clone();
                int cnt = 0;
                for (int j = 0; j < N; ++j) {
                    if ((i >> j & 1) == 1) {
                        turn(0, j);
                        ++cnt;
                    }
                }
                for (int x = 1; x < N; ++x) {
                    for (int y = 0; y < N; ++y) {
                        if (!g[x - 1][y]) {
                            turn(x, y);
                            ++cnt;
                        }
                    }
                }
                for (int j = 0; j < N; ++j) {
                    if (!g[4][j]) continue outer;
                }
                ans = Math.min(ans, cnt);
            }
            System.out.println(ans > 6 ? -1 : ans);
        }
    }
}

---

1. 灯 $(i-1, j)$ 的状态只能被 $(i-2, j), (i-1, j-1), (i-1, j), (i-1, j+1), (i, j)$ 改变，而此时前四个坐标的灯已经被枚举并决定操作过了，不会再枚举一遍，所以只剩 $(i, j)$ 这最后一次机会可以更改它的状态了。 ↩︎