alan23273850 的刷題筆記
b185: 6. 按鈕問題
Tags: puzzle
出處：https://zerojudge.tw/ShowProblem?problemid=b185
提交：https://zerojudge.tw/Submissions?problemid=b185&account=allllllan123456
問題：給定一個大小為 n * m (n, m $\in[1,6]$) 的方格組，每個方格上都有一顆按鈕，每顆按鈕只可以是凸起或壓下的狀態，當我們按下一顆按鈕的同時，除了自己這顆的狀態會改變之外，周圍上下左右的四顆按鈕 (如果存在) 的狀態也會隨之改變。那現在給定一個初始狀態，請問最少要按下幾顆不同的按鈕才能使得所有的按鈕都變成壓下的狀態？
解法：就是 DFS，但這種按鈕 (或開關燈) 問題比較特別一點，只有第一個列的按鈕們需要任意嘗試，從第二個列以後的按鈕就只能根據它自己正上方按鈕的狀態來決定要按或不按，如果正上方按鈕已經壓下，那現在這顆按鈕就不能動；反之如果正上方按鈕尚未壓下，那現在這顆按鈕就必須被觸發，所以最多只需要嘗試 $2^m$ 種組合即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n, m, miN;
5string button[6];
6
7void press(int x, int y) {
8 int dx[] = {0,-1,1,0,0}, dy[] = {0,0,0,-1,1};
9 for (int i=0; i<5; i++) {
10 int x2 = x + dx[i], y2 = y + dy[i];
11 if (0<=x2 && x2<n && 0<=y2 && y2<m)
12 button[x2][y2] = 'O'+'X' - button[x2][y2];
13 }
14}
15
16void dfs(int index, int times) {
17 if (times >= miN) return;
18 if (index == n*m) {
19 for (int i=0; i<m; i++)
20 if (button[n-1][i] == 'O')
21 return;
22 if (times < miN) miN = times;
23 return;
24 }
25 if (index<m || button[index/m-1][index%m]=='X')
26 dfs(index + 1, times);
27 if (index<m || button[index/m-1][index%m]=='O') {
28 press(index/m, index%m);
29 dfs(index + 1, times + 1);
30 press(index/m, index%m);
31 }
32}
33
34int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
35 while (cin >> n >> m) {
36 for (int i=0; i<n; i++) cin >> button[i];
37 miN = INT_MAX; dfs(0, 0);
38 cout << (miN == INT_MAX ? "Can not" : "Minimum Steps :" + to_string(miN)) << '\n';
39 }
40 return 0;
41}