Gym 100553J Jokewithpermutation(dfs)

题意：有n个数(n<=50)写在一行，将两数之间的空格去掉得到一个数字串。根据这个数字串回复原数；

思路：先求数的个数，当串长度小于10时，均为个位数；当串长度大于9时，存在两位数，剪去9个个位数，同样得到数的个数；

        数的个数也是串中的最大数；

        采用枚举的方法将每个数与串中的位置匹配，属于同一个数的数字对应同一个数；

        输出时，两位数的数字间不加空格；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str[105];
int len,mark;
int vis[505];
void dfs(int n)
{if(n==0){mark=1;return;}if(mark) return;if(n>=10){char temp1=n/10+'0';char temp2=n%10+'0';for(int i=0;i<len-1;i++){if(!vis[i]&&!vis[i+1]&&str[i]==temp1&&str[i+1]==temp2){vis[i]=n;vis[i+1]=n;dfs(n-1);if(mark) return;vis[i]=0;vis[i+1]=0;}}}else{for(int i=0;i<len;i++){if(!vis[i]&&(str[i]-'0')==n){vis[i]=n;dfs(n-1);if(mark) return;vis[i]=0;}}}
}
int main()
{int i,j,k,num;freopen("joke.in","r",stdin);freopen("joke.out","w",stdout);while(scanf("%s",&str)!=EOF){len=strlen(str);memset(vis,0,sizeof(vis));mark=0;if(len<10){num=len;}elsenum=(len-9)/2+9;dfs(num);printf("%c",str[0]);for(i=1;i<len;i++){if(vis[i]==vis[i-1])printf("%c",str[i]);else printf(" %c",str[i]);}printf("\n");}return 0;
}