Forming the habit of turning off the lights regularly can effectively save energy.
In a 10x10 matrix, 100 light bulbs and switches are placed. The design of these switches works as follows: when you press the switch of a particular light bulb, that light bulb and the bulbs above, below, to the left, and the right of it will also be toggled simultaneously. Toggling means that a light will change from on to off or from off to on. If the switch you press is at the edge of the matrix, only the bulbs above, below, to the left, and to the right (where bulbs exist) will be toggled simultaneously.
Below are two smaller examples. "O" represents a light bulb that is on, and "#" represents a light bulb that is off. When the switch in the center is pressed, the bulbs change as follows:
### #O#
### –> OOO
### #O#
### #O#
OOO –> ###
### #O#
The problem is: Given a 10x10 light bulb matrix, what is the minimum number of switch presses required to turn off all the bulbs?
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains a positive integer (≤ 10) representing the number of test cases. Each test case consists of a 10x10 matrix. There is a blank line separating each test case and matrix (please refer to the sample input). | For each test case, output a single line with the minimum number of switch presses required. |
| 3 ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO #O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO ########O# | 0 44 4 |
Thought Process
Use DFS to explore all possible combinations of switching on and off the bulbs in the first row. For each new configuration generated, evaluate the subsequent 9 rows. For each row, decide whether to toggle a switch based on whether the bulb directly above it needs to be turned off. After evaluating all 9 rows, check if all the bulbs are off (i.e., each character is #). Determine and record the minimum number of switch presses required.
Sample Code－ZeroJudge B002: Turn Off the Lights
#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