这题想必大家看到都知道是个dfs搜索问题...
怎么构建思路呢？题目给了我们方向了，一个是顺子，还有一个是刻子，我们分别进行顺子和刻子的判断即可，这就是两个回溯的操作。
我们如何开始呢？可以对1-9中的每一个牌（已有的个数要小于4），加一张进去看成功和牌么，如果和了就输出。
判断赢牌的思路就是先把雀头拿出来，然后进行dfs。
这里阅读了一篇博客：
其实回溯我自己踩了个坑，代码如下所示：
#include <bits/stdc++.h>
using namespace std;
int state[10];
int rec;
bool dfs(int state[], int n){
if (n==0) return true;
for (int i = 1; i <= 9; ++i) {
if (state[i]>=3){
state[i]-=3;
if (dfs(state, n-3)){
rec=1;
}
state[i]+=3;
}
if (rec) return true;
if (i>=1&&i<=7&&state[i]>0&&state[i+1]>0&&state[i+2]>0){
state[i]--;
state[i+1]--;
state[i+2]--;
if (dfs(state, n-3)){
rec=1;
}
state[i]++;
state[i+1]++;
state[i+2]++;
}
if (rec) return true;
}
return false;
}
bool isWin(int state[]){
for (int i = 1; i <= 9; ++i) {
if (state[i]>=2){
state[i]-=2;
rec=0;
dfs(state, 12);
state[i]+=2;
if (rec){
return true;
}
//注意回溯一定要在dfs之后立马回溯 如果放在这个位置有可能减了然后提前返回导致state数目错误
}
}
return false;
}
int main() {
memset(state,0,sizeof(state));
for (int i = 0; i < 13; ++i) {
int tmp;
cin>>tmp;
state[tmp]++;
}
int flag=0;
for (int i = 1; i <= 9; ++i) {
if (state[i]>=4){
continue;
}
state[i]++;
if (isWin(state)){
if (!flag){
cout<<i;
}else{
cout<<" "<<i;
}
flag=1;
}
state[i]--;
}
if (!flag){
cout<<0;
}
cout<<endl;
return 0;
}
