UVa 321

UVa 321

題目

http://domen111.github.io/UVa-Easy-Viewer/?321

在一個房子裡面有 $r$ 個房間、 $d$ 個通道以及 $s$ 個電燈開關

告訴你這 $d$ 個通道分別連接哪兩個房間,以及這 $s$ 個電燈開關位在哪個房間,分別可以控制哪個房間的電燈

現在有個人在編號 $1$ 的房間當中,想要走到編號 $r$ 的房間,並且由於他怕黑,經過的房間必定要是有開燈的才可以進入

每次可以選擇要觸發在當前房間有的開關,或是要走到下一個房間

編號 $1$ 的房間燈一開始是開的狀態,請問最少需要多少的操作可以走到編號 $r$ 的房間,並且輸出其過程

想法

因為要找的是最少的操作數,所以可以想到用 BFS 來解

題目要求當前所在房間的燈要是開的,所以當前在哪個房間是重要的狀態
並且當前有哪些燈是開著的也會影響到未來的發展

所以對於這一題有兩個狀態 所在房間編號 以及 所有房間燈的狀態

至於轉移則有兩種方式

  • 第一種是移動到有連接的房間,需要保證下個房間燈是開的
  • 第二種是切換某個房間的電燈開關,需要確保不會關到自己的燈

有了狀態以及轉移,接下來只要確保每次轉移的狀態過去都沒有出現過即可

這一題我用數字的每個 bit 去記錄 房間燈開關的狀態 以及 房間 x 可以操作哪個房間的電燈

轉移當中的切換開關就可以使用位元運算去找到下一個可行的點(詳細看程式碼)

至於回朔的方式,這一題我是用遞迴

在 BFS 轉移的過程當中去紀錄 從誰轉移過來

因為我是用陣列去模擬 queue ,所以資料都會留著,就可以直接紀錄是從陣列的哪個 index 轉移過來即可

至於要判斷是哪個操作,我們可以觀察 房間燈開關的狀態

如果前後狀態相同就是走到下一個房間

如果有個房間燈狀態從 $0 \to 1$,那就是開燈,反之就是關燈

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//By Koios1143
#include<iostream>
using namespace std;
int r, d, s, ans, Case=1, edge_len[15], io[15], edge[15][15];
int que_id[40000], que_light[40000], from[40000], room_id[3000];
bool vis[15][3000];

int BFS(){
// 一開始的房間是在編號 1
// 一開始房間 1 的燈是開的,所以 2^1 的位置要是 1
que_id[0] = 1;
que_light[0] = 2;
vis[1][2] = true;

for(int head=0, tail=1, id, light ; head<tail ; head++){
id = que_id[head];
light = que_light[head];

// 找到答案要確保只有編號 r 的房間燈是亮的
if(id == r && light == (1<<r)){
return head;
}

// 走到下一個房間
for(int i=0 ; i<edge_len[id] ; i++){
if(!vis[edge[id][i]][light] && (light & (1<<edge[id][i])) > 0){
que_id[tail] = edge[id][i];
que_light[tail] = light;
from[tail] = head;
tail++;
}
}

// 切換開關
// i&=~lowbit 會讓 i 當中最低位的 1 變成 0,其他不變
for(int i=io[id], lowbit, nxt_light ; i!=0 ; i&=~lowbit){
lowbit = (i & -i); // 取得 i 最低位的位置
nxt_light = light ^ lowbit; // 得到可以操作的開關
// 切換前要先確認不會關到自己當前的房間燈
if(!vis[id][nxt_light] && (nxt_light & (1<<id))!=0){
vis[id][nxt_light] = true;
que_id[tail] = id;
que_light[tail] = nxt_light;
from[tail] = head;
tail++;
}
}
}
return -1;
}

void print_ans(int step, int cur_idx){
if(from[cur_idx] == -1){
cout<<"The problem can be solved in "<<step<<" steps:\n";
return;
}
int pre_idx = from[cur_idx];
print_ans(step+1, pre_idx);

if(que_light[pre_idx] == que_light[cur_idx]){
// 操作是走到下個房間
cout<<"- Move to room "<<que_id[cur_idx]<<".\n";
}
else{
// 操作是切換開關
// 透過 xor 可以剩下被切換的房間是 1
// 透過預先建好的表對應到房間 id
// 也可以改用 log (以二為底)
int room = room_id[que_light[cur_idx] ^ que_light[pre_idx]];
if((que_light[cur_idx] & (1<<room)) == 0){
// off
cout<<"- Switch off light in room "<<room<<".\n";
}
else{
// on
cout<<"- Switch on light in room "<<room<<".\n";
}
}
}

int main(){
for(int i=0 ; i<=10 ; i++){
// 將燈的值轉換成房間 id
room_id[1<<i] = i;
}
while(cin>>r>>d>>s && (r!=0 || d!=0 || s!=0)){
// 初始化
from[0] = -1;
for(int i=0 ; i<15 ; i++){
edge_len[i] = io[i] = 0;
for(int j=0 ; j<3000 ; j++){
vis[i][j] = false;
}
}

// 將每條邊用類似 list 的方式儲存比較方便
// 每條 list 的長度紀錄在 edge_len[]
for(int i=0, a, b ; i<d ; i++){
cin>>a>>b;
edge[a][edge_len[a]++] = b;
edge[b][edge_len[b]++] = a;
}
// 利用每個 bit 去記錄房間 a 的開關控制的房間
for(int i=0, a, b ; i<s ; i++){
cin>>a>>b;
io[a] |= (1<<b);
}

ans = BFS();
cout<<"Villa #"<<Case++<<"\n";
if(ans == -1){
cout<<"The problem cannot be solved.\n";
}
else{
print_ans(0, ans);
}
cout<<"\n";
}

return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(d + s)$

每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $(d \times 2^s) \times (s + d)$,大約是 $O(2^s)$

每筆測資遞迴求解時間複雜度為 $O(r)$

每筆測資總時間複雜度為 $O(2^s)$