養成隨時關燈的好習慣能有效地節省能源。
在一個 10 * 10 的矩陣中，共安置了 100 個燈泡與開關，這些開關的設計是這樣的：當你按下某個燈泡的開關時，此燈泡及其上、下、左、右的燈泡也會同時被切換，所謂切換就是亮變暗或暗變亮；而當你按的燈泡開關是在矩陣的邊緣時，就只有其上、下、左、右有燈泡的地方會被同時切換。
以下是兩個比較小的例子，「O」表示燈泡是亮的，「#」表示燈泡是暗的，當按下正中間的開關時，燈泡的變化如下：
### #O#
### –> OOO
### #O#
### #O#
OOO –> ###
### #O#
這一題的問題是：給你一個 10 * 10 的燈泡矩陣，若要將所有的燈泡變暗，最少要按幾次開關。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一列有一個正整數 (<= 10) 代表共有多少組測試資料。每一組測試資料是一個 10 * 10 的矩陣。測試組數及矩陣之間皆間隔一列 (請參考範例輸入)。 | 對每一組測試資料輸出一列，輸出需按開關的最少次數。 |
| 3 ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO #O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO ########O# | 0 44 4 |
解題思路
使用 DFS 的方式將第一行的字串做每一種開和關的可能性列出來，並且每一次得出一種新排法時就判斷下面的 9 行，下面的每一行都依照目前位置的正上方是否有需要關掉的燈泡為依據是否要進行開關。當 9 行都判斷完之後就判斷是不是每一個字元都是 #，並且找出最少的開關次數。
範例程式碼－ZeroJudge B002: 關燈
#include <iostream>
using namespace std;
string light[50] = {};
int ans = -999, loc[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char change(const char ch) {
if (ch == '#') return 'O';
return '#';
}
void rest(string *lightbulb, int button) {
string *save = lightbulb;
for (int i = 1; i<10; i++) {
for (int j = 0; j<10; j++) {
if (lightbulb[i-1][j] == 'O') {
button++;
lightbulb[i][j] = change(lightbulb[i][j]);
for (int k = 0; k<4; k++) {
const int y = i+loc[k][0], x = j+loc[k][1];
if (y >= 0 && y < 10 && x >= 0 && x < 10) lightbulb[y][x] = change(lightbulb[y][x]);
}
}
}
}
bool ok = true;
for (int i = 0; i<10; i++) {
for (int j = 0; j<10; j++) {
if (lightbulb[i][j] == 'O') {
ok = false;
break;
}
}
}
if (ok) {
if (ans == -999 || button < ans) ans = button;
}
lightbulb = save;
}
void firstLine(string *lightbulb, const int begin, const int button) {
string buffer[10];
for(int i = 0; i < 10; i++) {
buffer[i] = lightbulb[i];
}
buffer[0][begin] = change(buffer[0][begin]);
for (int j = 0; j<4; j++) {
const int y = 0+loc[j][0], x = begin+loc[j][1];
if (y >= 0 && y < 10 && x >= 0 && x < 10) buffer[y][x] = change(buffer[y][x]);
}
if(begin < 9) {
firstLine(buffer, begin+1, button+1);
firstLine(lightbulb, begin+1, button);
}
else {
rest(buffer , button+1);
rest(lightbulb , button);
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++) {
ans = -999;
for (int j = 0; j<10; j++) cin >> light[j];
firstLine(light, 0, 0);
cout << ans << "\n";
}
}
//ZeroJudge B002
//Dr. SeanXD