[[411620]]

題目來(lái)源 AcWing[1]。

題目

你玩過(guò)“拉燈”游戲嗎?

盞燈排成一個(gè) 的方形。

每一個(gè)燈都有一個(gè)開(kāi)關(guān)，游戲者可以改變它的狀態(tài)。

每一步，游戲者可以改變某一個(gè)燈的狀態(tài)。

游戲者改變一個(gè)燈的狀態(tài)會(huì)產(chǎn)生連鎖反應(yīng)：和這個(gè)燈上下左右相鄰的燈也要相應(yīng)地改變其狀態(tài)。

我們用數(shù)字 表示一盞開(kāi)著的燈，用數(shù)字 表示關(guān)著的燈。

下面這種狀態(tài)

10111 
01101 
10111 
10000 
11011 

在改變了最左上角的燈的狀態(tài)后將變成：

01111 
11101 
10111 
10000 
11011 

再改變它正中間的燈后狀態(tài)將變成：

01111 
11001 
11001 
10100 
11011 

給定一些游戲的初始狀態(tài)，編寫(xiě)程序判斷游戲者是否可能在 步以內(nèi)使所有的燈都變亮。

輸入格式

第一行輸入正整數(shù) ，代表數(shù)據(jù)中共有 個(gè)待解決的游戲初始狀態(tài)。

以下若干行數(shù)據(jù)分為 組，每組數(shù)據(jù)有 行，每行 個(gè)字符。

每組數(shù)據(jù)描述了一個(gè)游戲的初始狀態(tài)。

各組數(shù)據(jù)間用一個(gè)空行分隔。

輸出格式

一共輸出 行數(shù)據(jù)，每行有一個(gè)小于等于 的整數(shù)，它表示對(duì)于輸入數(shù)據(jù)中對(duì)應(yīng)的游戲狀態(tài)最少需要幾步才能使所有燈變亮。

對(duì)于某一個(gè)游戲初始狀態(tài)，若 步以內(nèi)無(wú)法使所有燈變亮，則輸出 。

數(shù)據(jù)范圍

輸入樣例：

3 
00111 
01011 
10001 
11010 
11100 
 
11101 
11101 
11110 
11111 
11111 
 
01111 
11111 
11111 
11111 
11111 

輸出樣例：

3 
2 
-1 

題解

首先有三點(diǎn)很重要的性質(zhì)需要說(shuō)明：

• 如果按哪些燈確定了，那么按這些燈的順序不重要，無(wú)論什么順序，結(jié)果都是相同的
• 我們沒(méi)有必要按一盞燈兩次及以上，因?yàn)?，按兩次，相?dāng)于沒(méi)按，按三次，相當(dāng)于按兩次+一次(也就是一次)

因此：

• 因?yàn)榘礋舻捻樞虿恢匾?，我們可以先把第一行的燈都按?/li>
• 我們發(fā)現(xiàn)，第一行想按的燈都按過(guò)之后，如果想要讓第一行全亮，那么我第二行只能有一種按法，就是按第一行不亮的燈的下面的燈(下面是例子)

第一行狀態(tài) 10011 （1代表亮的燈） 
第二行動(dòng)作 01100 （1代表按按鈕） 

那么，我們?cè)趺幢ＷC第二行全亮呢?只能用第三行來(lái)解決!

那么，我們?cè)趺幢ＷC最后一行(第五行)全亮呢?沒(méi)法保證!

我們發(fā)現(xiàn)，如果第一行按法確定了，那么接下來(lái)二三四五行的按法和能不能全亮就確定了。

因此，對(duì)于任意一種輸入狀態(tài)，我們把第一行 32 種按法全部遍歷一遍，看看哪些可以全亮(通過(guò)檢測(cè)第五行狀態(tài))，這些全亮的種有沒(méi)有操作次數(shù)小于等于 6 的。有的話，就返回這個(gè)操作數(shù)，否則就返回 -1 唄。

代碼

#include <iostream> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
 
const int N = 5 + 5;   // 加上 5 更保險(xiǎn) 
// 注意接收時(shí)用字符串更方便，因?yàn)檩斎肓髅啃袥](méi)有空格 
char g[N][N];  // 記錄燈目前的情況 
 
// 上右下左中 
int dx[5] = {0, 1, 0, -1, 0}; 
int dy[5] = {1, 0, -1, 0, 0}; 
 
// 按第 x 行第 y 列，本身和上下左右五個(gè)燈都取反 
void turn(int x, int y) 
{ 
    for (int i = 0; i < 5; ++ i) 
    { 
        int a = x + dx[i], b = y + dy[i]; 
        if (0 <= a && a < 5 && 0 <= b && b < 5) 
            g[a][b] = g[a][b] == '1' ? '0': '1'; 
    } 
} 
 
int work() 
{ 
    int ans = 2e9; 
    // 第一層循環(huán)，把所有第一行按的情況都遍歷 
    // k 是被壓縮了的狀態(tài)，最小 0b00000 代表都不按， 
    // 最大 0b11111 代表都按 
     
    // 備份，因?yàn)橄旅娴牟僮鲿?huì)改變 g 
    char backup[N][N]; 
    memcpy(backup, g, sizeof g); 
 
    for (int k = 0; k < (1 << 5); ++ k) 
    { 
        // 確保我們的 g 是輸入的 g 
        memcpy(g, backup, sizeof backup); 
 
        // 當(dāng)?shù)谝恍袨?nbsp;k 時(shí)，總操作次數(shù)是.. 
        int res = 0;  // 用 res 來(lái)記錄 
 
        // 執(zhí)行 k （根據(jù) k 把第一行按了） 
        for (int j = 0; j < 5; ++ j) 
        { 
            if (k >> j & 1) 
            { 
                res ++; 
                turn(0, j); 
            } 
        } 
         
        // 第一行確定了，第二行就確定了 
        // 因?yàn)橹挥泻侠聿僮鞯诙?nbsp;
        // 才能把第一行全部點(diǎn)亮 
        // 以此類(lèi)推，第二行定了后，第三行就被第二行決定了 
        for (int i = 0; i < 4; ++ i) 
        { 
            for (int j = 0; j < 5; ++ j) 
            { 
                if (g[i][j] == '0') 
                { 
                    res ++; 
                    turn(i + 1, j); 
                } 
            } 
        } 
 
        // 上面的操作一定能保證前 4 行全亮 
        // 但是第 5 行不一定全亮，第 5 行全亮，才是真正有效的操作 
        bool success = true; 
        for (int j = 0; j < 5; ++ j) 
        { 
            if (g[4][j] == '0') 
            { 
                success = false; 
                break; 
            } 
        } 
         
        // 如果是有效的操作，咱看看一共按了幾次開(kāi)關(guān) 
        if (success) ans = min(res, ans); 
    } 
     
    // 根據(jù)題意返回輸出值 
    if (ans > 6) return -1; 
    return ans; 
} 
 
int main() 
{ 
    int n; 
    cin >> n; 
    while (n -- ) 
    { 
        for (int i = 0; i < 5; ++ i) cin >> g[i]; 
        printf("%d\n", work()); 
    } 
} 

參考資料

[1]

AcWing: https://www.acwing.com/