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
| #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(){ 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]; 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++; } } for(int i=io[id], lowbit, nxt_light ; i!=0 ; i&=~lowbit){ lowbit = (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{ int room = room_id[que_light[cur_idx] ^ que_light[pre_idx]]; if((que_light[cur_idx] & (1<<room)) == 0){ cout<<"- Switch off light in room "<<room<<".\n"; } else{ cout<<"- Switch on light in room "<<room<<".\n"; } } }
int main(){ for(int i=0 ; i<=10 ; i++){ 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; } } for(int i=0, a, b ; i<d ; i++){ cin>>a>>b; edge[a][edge_len[a]++] = b; edge[b][edge_len[b]++] = 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)$