# UVA 11210 - Chinese Mahjong 題目連結: [Lucky Cat](http://luckycat.kshs.kh.edu.tw/homework/q11210.htm) [Uva](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2151) 這題敘述有點繁雜...也很難簡單說明 還是麻煩點[Lucky Cat](http://luckycat.kshs.kh.edu.tw/homework/q11210.htm)進去看看吧 麻將還真是有夠麻煩的... 研究題目約10~20分鐘 觀察了一下，其實測資憑感覺不大，所以就想要BFS暴力解 就直接實作了 ## 大概做法: 1. 將34個牌(1S、4T、NAN...) 換成電腦容易儲存判斷的數字編號 在此是將他們視作0~33 2. 依據題目需求，我們可以得知比較需要的資訊是每個牌的數量，因此記錄下來 3. 開始依據儲存的資料BFS 依據題意，如果是聽牌的狀態，那麼一定可以拆成好幾組面子的和一組不完整缺一個的面子 因此，只要BFS拆現有的面子，拆到最後剩下不能再拆，判斷是否可以組成另一個面子即可 ## 詳細作法: ```cpp= #define card_size 34//共34種牌 ``` 首先這題一個蠻常用的值我先define了 避免打一堆34哪裡打錯或是怎樣害我找不出bug 這代表牌組的總數目 ```cpp= struct Card { int num[card_size],all_num=13; }; ``` 儲存一個牌組的結構，分別記錄這個牌組的每個牌有多少數量,總共有幾個 ```cpp= queue<Card> toBFS; toBFS.push(card); ``` toBFS是要暴力BFS用的佇列 把儲存牌組數量的結構一一丟進去 讓他一一往下搜尋 ```cpp= Card x=toBFS.front(); toBFS.pop(); ``` 進入到BFS裡面，用x來判斷下一個要丟進toBFS的、或是是否達到聽牌 toBFS就pop掉了 ```cpp= for(int i=0;i<card_size;i++) { if(x.num[i]>=3) { x.num[i]-=3; x.all_num-=3; toBFS.push(x); x.num[i]+=3; x.all_num+=3; } if(i<27&&i%9>1&&x.num[i]&&x.num[i-1]&&x.num[i-2])//chow { for(int j=i-2;j<=i;j++)x.num[j]--; x.all_num-=3; toBFS.push(x); for(int j=i-2;j<=i;j++)x.num[j]++; x.all_num+=3; } } ``` 在BFS裡面開始用儲存牌組資料的x往下搜， 只要滿足題目敘述的就可以往下搜尋 ```cpp= if(x.all_num==1) for(int i=0;i<card_size;i++) if(x.num[i]) ans[i]=true; if(x.all_num==2) { for(int i=0;i<card_size;i++) { if(x.num[i]==2) { ans[i]=true; break; } else if(i<27&&i%9>1&&x.num[i]+x.num[i-1]+x.num[i-2]==2) ans[x.num[i]?x.num[i-1]?i-2:i-1:i]=true; } } ``` 往下搜到最底的時候，判斷x牌組，找出是否有沒有聽某張牌 基本上這樣整體BFS就大概完成了 ```cpp= if(ans[i]&&card.num[i]!=4) { cout<<' '<<card_name[i]; isnt_ready=0; } ``` 如果原本某張牌的數量為4，就算BFS結果為對，他也無法聽牌 因為最多只有4張牌，都在他手上了 ## 完整程式碼 ```cpp= #include<iostream> #include<cstring> #include<queue> using namespace std; #define card_size 34//共34種牌 //紀錄牌類名字，方便輸出 const string card_name[card_size]= {"1T","2T","3T","4T","5T","6T","7T","8T","9T", "1S","2S","3S","4S","5S","6S","7S","8S","9S", "1W","2W","3W","4W","5W","6W","7W","8W","9W", "DONG","NAN","XI","BEI","ZHONG","FA","BAI"}; //紀錄正在聽甚麼牌、以及是否在聽牌 bool ans[card_size],isnt_ready=1; //一個紀錄每個card數量及總數的struct struct Card { int num[card_size],all_num=13; }card; inline void Init()//初始化 (用於每次結束，把卡片數量歸零避免判斷到上次的) { memset(card.num,0,sizeof(card.num)); memset(ans,0,sizeof(ans)); card.all_num=13; isnt_ready=1; return; } //把字串轉成卡片ID，再記錄該ID的數量 (用於一開始輸入，轉換成可用資料) inline void string_to_card_num(string k) { if(k[0]>='1'&&k[0]<='9') card.num[k[0]-'1'+(k[1]=='T'?0:(k[1]=='S'?9:18))]++; else for(int i=27;i<card_size;i++) if(k==card_name[i])card.num[i]++; return ; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); int Case=1;//第幾筆測資 string input_card[13];//牌組 while(cin>>input_card[0]) { if(input_card[0]=="0")break; //紀錄牌組內容 string_to_card_num(input_card[0]); for(int i=1;i<13;i++) { cin>>input_card[i]; string_to_card_num(input_card[i]); } //BFS用佇列，把card和已吃過eye的丟進去 queue<Card> toBFS; toBFS.push(card); //題目需求應該不能超出一次eye，所以要在BFS外丟eye for(int i=0;i<card_size;i++) { if(card.num[i]>=2) { card.num[i]-=2; card.all_num-=2; toBFS.push(card); card.num[i]+=2; card.all_num+=2; } } //開始BFS //這裡有個問題，沒有紀錄已走過的地方，所以會搜尋較多次，時間較長，待改善 while(!toBFS.empty()) { Card x=toBFS.front(); toBFS.pop(); //剩1張，可以用eye作為聽牌 if(x.all_num==1) for(int i=0;i<card_size;i++) if(x.num[i]) ans[i]=true; //剩2張，可能可以用pong或chow或都不是作為聽牌 if(x.all_num==2) { for(int i=0;i<card_size;i++) { if(x.num[i]==2)//當有某個種類有2張時，可以達成pong { ans[i]=true; break; } //如果可以達成特定3個連續，可以達成chow else if(i<27&&i%9>1&&x.num[i]+x.num[i-1]+x.num[i-2]==2) ans[x.num[i]?x.num[i-1]?i-2:i-1:i]=true; } } for(int i=0;i<card_size;i++) { if(x.num[i]>=3)//pong { x.num[i]-=3;//把pong的丟進queue x.all_num-=3;//總數一樣扣掉 toBFS.push(x); x.num[i]+=3;//加回來，繼續之後的判斷 x.all_num+=3; } if(i<27&&i%9>1&&x.num[i]&&x.num[i-1]&&x.num[i-2])//chow { for(int j=i-2;j<=i;j++)x.num[j]--; x.all_num-=3; toBFS.push(x); for(int j=i-2;j<=i;j++)x.num[j]++; x.all_num+=3; } } //*測試用*/for(int i=0;i<card_size;i++)cout<<x.num[i]<<' ';cout<<endl; } //輸出部分 cout<<"Case "<<Case++<<':'; for(int i=0;i<card_size;i++) if(ans[i]&&card.num[i]!=4) { cout<<' '<<card_name[i]; isnt_ready=0; } if(isnt_ready)cout<<" Not ready"; cout<<'\n'; Init();//初始化 } return 0; } ``` ## 心得 這題我猜應該正解是DP吧 BFS畢竟是暴力解的方法... 雖然我丟上去是0.000s就是了 其中認為還有些可以改良的地方 像是BFS過程中重複判斷的太多了 因為沒有像一些BFS用visited之類的方法紀錄避免重複判斷，資料太多了 雖然不會無窮迴圈，因為牌組總數量越來越小 但總之可以在優化...只是一時還想不到簡單好寫的方法... 大概就這樣 接著可以慢慢思考其他解法吧 如果測資更大，變成100個、1000個牌或更多 可能真的就DP解吧 或是這題真的本來就暴力解... DP是純粹我想太多