題目連結
題目大意：
有一塊板子，長寬不超過5。按其中一個按鈕，周遭九宮格內的按鈕會依照他給訂的亮暗做變化。求最少按了哪幾個按鈕後，板子會全亮。
題目思路：
首先，這個題目個發現，按按鈕的順序並不影響最後的結果。
所以我從按鈕(1, 1)開始做DFS，按(1, 1)、不按(1, 1) -> 按(1, 2)、不按(1, 2) -> 按(1, 3)、不按(1, 3)....這樣接著下去
中間有個bound的方法，若我現在要按這個按鈕，可是前兩行有不亮的，代表接下來他一定不會再亮，停止DFS。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include < cstdio>#include < string.h>#include < math.h>#include < iostream>using namespace std;int light[4][4], panel[6][6], ans_arr[26], path[26];int dir[9][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};int row, col, ans;void init(){ memset(panel, 0, sizeof(panel)); ans = row*col+1;}int push(int butt_r, int butt_c){ if (butt_r>=3) for (int i=1; i<=col; i++) if (!panel[butt_r-2][i]) return 0; int push_r, push_c; for (int i=0; i< 9; i++) { push_r = butt_r+dir[i][0]; push_c = butt_c+dir[i][1]; if (light[dir[i][0]+2][dir[i][1]+2] && push_r<=row && push_r>=1 && push_c<=col && push_c>=1) panel[push_r][push_c] = !panel[push_r][push_c]; } return 1;}void dfs(int x, int y, int count){ int butt = (x-1)*col+y; if (count>=ans) return; if (butt>row*col){ for (int i=1; i<=row; i++) for (int j=1; j<=col; j++) if (!panel[i][j]) return; ans = count; for (int i=0; i< ans; i++) ans_arr[i] = path[i]; return; } int n_x = (y==col)?x+1:x; int n_y = (y==col)?1:y+1; if (!push(x, y)) return; path[count++] = butt; dfs(n_x, n_y, count); if (!push(x, y)) return; count--; dfs(n_x, n_y, count);}int main() { int case_count=1; string in; while (scanf("%d%d", &row, &col) && row) { init(); printf("Case #%d\n", case_count++); for (int i=1; i<=3; i++) { cin >> in; light[i][1] = (in[0]=='*')?1:0; light[i][2] = (in[1]=='*')?1:0; light[i][3] = (in[2]=='*')?1:0; } dfs(1, 1, 0); if (ans==row*col+1) printf("Impossible.\n"); else{ printf("%d", ans_arr[0]); for (int i=1; i< ans; i++) printf(" %d", ans_arr[i]); printf("\n"); } } return 0;} |
