問題描述

有一個(gè)由按鈕組成的矩陣, 其中每行有 6 個(gè)按鈕, 共5 行。每個(gè)按鈕的位置上有一盞燈。當(dāng)按下一個(gè)按鈕后,該按鈕以及周圍位置(上邊、下邊、左邊、右邊)的燈都會(huì)改變一次。即,如果燈原來是點(diǎn)亮的,就會(huì)被熄滅;如果燈原來是熄滅的,則會(huì)被點(diǎn)亮。在矩陣角上的按鈕改變 3 盞燈的狀態(tài);在矩陣邊上的按鈕改變 4 盞燈的狀態(tài);其他的按鈕改變 5 盞燈的狀態(tài)。在下圖 1 中,左邊矩陣中用 X 標(biāo)記的按鈕表示被按下,右邊的矩陣表示燈狀態(tài)的改變。與一盞燈毗鄰的多個(gè)按鈕被按下時(shí),一次操作會(huì)抵消另一次操作的結(jié)果。在圖 2 中,第 2行第 3、5 列的按鈕都被按下,因此第 2 行、第 4 列的燈的狀態(tài)就不改變。根據(jù)上面的規(guī)則,我們知道:

1. 第 2 次按下同一個(gè)按鈕時(shí),將抵消第 1 次按下時(shí)所產(chǎn)生的結(jié)果。因此,每個(gè)按鈕最多只需要按下一次。
2. 各個(gè)按鈕被按下的順序?qū)ψ罱K的結(jié)果沒有影響。
3. 對(duì)第 1 行中每盞點(diǎn)亮的燈,按下第 2 行對(duì)應(yīng)的按鈕,就可以熄滅第 1 行的全部燈。如此重復(fù)下去,可以熄滅第 1、2、3、4 行的全部燈。同樣,按下第 1、2、3、4、5 列的按鈕,可以熄滅前 5 列的燈。

對(duì)矩陣中的每盞燈設(shè)置一個(gè)初始狀態(tài)。請(qǐng)你寫一個(gè)程序,確定需要按下哪些按鈕,恰好使得所有的燈都熄滅。

熄燈問題

輸入

第一行是一個(gè)正整數(shù) N,表示需要解決的案例數(shù)。每個(gè)案例由 5 行組成,每一行包括 6個(gè)數(shù)字。這些數(shù)字以空格隔開,可以是 0 或 1。0 表示燈的初始狀態(tài)是熄滅的,1 表示燈的初始狀態(tài)是點(diǎn)亮的。

輸出

對(duì)每個(gè)案例,首先輸出一行,輸出字符串“PUZZLE #m”,其中 m 是該案例的序號(hào)。接著按照該案例的輸入格式輸出 5 行,其中的 1 表示需要把對(duì)應(yīng)的按鈕按下,0 則表示不需要按對(duì)應(yīng)的按鈕。每個(gè)數(shù)字以一個(gè)空格隔開。

輸入樣列

2
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
0 0 1 0 1 0
1 0 1 0 1 1
0 0 1 0 1 1
1 0 1 1 0 0
0 1 0 1 0 0

輸出樣例

PUZZLE #1
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
PUZZLE #2
1 0 0 1 1 1
1 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 0 1 1 0 1

算法實(shí)現(xiàn)

using System;

namespace Questions{
    class Program{
        public static void Main(string[] args){
            int n = int.Parse(Console.ReadLine());
            for (int k = 1; k <= n; k++)
            {
                int[,] num = new int[6, 8];
                for (int i = 1; i < 6; i++)
                {
                    string input = Console.ReadLine();
                    string[] data = input.Split();
                    for (int j = 1; j < 7; j++)
                        num[i, j] = int.Parse(data[j - 1]);
                }
                int[,] result = new int[6, 8];
                int l = 0;
                while (!IsSuccess(num, ref result))
                {
                    result[1, 1]++;
                    l = 1;
                    while (result[1, l] > 1)
                    {
                        result[1, l] = 0;
                        result[1, ++l]++;
                    }
                }

                Console.WriteLine("PUZZLE #{0}", k);
                for (int i = 1; i < 6; i++)
                {
                    for (int j = 1; j < 7; j++)
                    {
                        Console.Write("{0} ", result[i, j]);
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
            Console.ReadKey();
        }
        public static bool IsSuccess(int[,] num, ref int[,] result)
        {
            for (int i = 1; i < 5; i++)
                for (int j = 1; j < 7; j++)
                    result[i + 1, j] = (num[i, j] + result[i, j] + result[i - 1, j] + result[i, j - 1] + result[i, j + 1]) % 2;
            for (int j = 1; j < 7; j++)
                if ((result[5, j] + result[5, j - 1] + result[5, j + 1] + result[4, j]) % 2 != num[5, j])
                    return false;
            return true;
        }
    }
}