首页 > 代码库 > LeetCode - Zuma Game
LeetCode - Zuma Game
class Solution {
public:
struct node{
char fs[25];
int fk[25];
int len ;
node(){
memset(fs,0,sizeof(fs));
memset(fk,0,sizeof(fk));
len = 0;
}
};
node del(node a){
node b;
for(int i = 0 ; i < a.len ; i++){
if(a.fk[i]>=3){
continue;
}
if(b.len>0&&b.fs[b.len-1]==a.fs[i]){
b.fk[b.len-1]+=a.fk[i];
continue;
}
b.fs[b.len]=a.fs[i];
b.fk[b.len]=a.fk[i];
b.len++;
}
if(b.len!=a.len)return del(b);
return b;
}
int vmin ;
void fuck(node a){
for(int i = 0 ; i < a.len ; i ++){
cout<<a.fs[i]<<a.fk[i]<<" ";
}
cout<<endl;
}
void dfs(node a,string hand,int step){
// fuck(a);
a = del(a);
// fuck(a);
// getchar();
if(a.len == 0){
if(vmin > step){
vmin = step;
}
return ;
}
for(int i = 0 ; i < a.len ;i ++){
for(int j = 0 ; hand[j] ; j ++){
if(hand[j]==‘!‘)continue;
if(hand[j]==a.fs[i]){
a.fk[i]++;
hand[j]=‘!‘;
dfs(a,hand,step+1);
hand[j]=a.fs[i];
a.fk[i]--;
}
}
}
}
int findMinStep(string board, string hand) {
vmin = 999;
node a;
for(int i = 0 ; board[i] ; i ++){
if(a.len>0 && a.fs[a.len-1]== board[i]){
a.fk[a.len-1]++;
continue;
}
a.fs[a.len] = board[i];
a.fk[a.len] = 1;
a.len++;
}
dfs(a,hand,0);
if(vmin!=999){
return vmin;
}
return -1;
}
};
LeetCode - Zuma Game