TOJ 362
題目
https://toj.tfcis.org/oj/pro/362/
現在有一副撲克牌,分成 $4$ 堆,每一堆都有 $13$ 張牌
現在我們要從 $4$ 個牌堆當中每次選兩張相同的拿出,最後是否有辦法把全部的牌拿完?
想法
我們可以枚舉在每一層當前的 $4$ 張牌當中要取哪兩張,把所有的情況列出,如果能將全部的牌取完就表示有答案,否則沒有
至於要如何知道牌堆中哪張牌是最上方的,我們可以用一個陣列去紀錄 $4$ 個牌堆最上方的牌是牌堆中的第幾張,如此一來要枚舉的時候就只需要改變紀錄的 index 即可
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
| #include<iostream> using namespace std; int arr[4][13]; int top[4]; bool found=false, ans=false;
void DFS(int depth){ if(depth == 26){ ans=true; found=true; return; } for(int i=0 ; i<4 ; i++){ for(int j=i+1 ; j<4 && !found ; j++){ if(top[i]<13 && top[j]<13 && arr[i][top[i]] == arr[j][top[j]]){ top[i]++; top[j]++; DFS(depth+1); top[i]--; top[j]--; } } } }
int main(){ for(int i=0 ; i<4 ; i++){ top[i] = 0; for(int j=0 ; j<13 ; j++){ cin>>arr[i][j]; } } DFS(0); if(ans){ cout<<"YES\n"; } else{ cout<<"NO\n"; } return 0; }
|
時間複雜度分析
令 $n = 4, m = 13$
輸入時間複雜度為 $O(nm)$
DFS 每層最多有 $4$ 種選擇,總共有 $26$ 層
DFS 時間複雜度為 $O(n^{2m})$
總時間複雜度為 $O(nm + n^{2m})$