计算之道 （置换的玩笑）搜索

小蒜头又调皮了。这一次，姐姐的实验报告慘遭毒手。

姐姐的实验报告上原本记录着从 1 到 n 的序列。随意两个数字间用空格间隔。

可是“坑姐”的蒜头竟然把数字间的空格都给删掉了。整个数字序列变成一个长度为 1 到 100 的且首部没有空格的数字串。

如今姐姐已经怒了。蒜头找你写个程序快点把试验数据复原。

输入

输入文件有一行，为一个字符串——被蒜头搞乱的实验数据。

字符串的长度在 1 到 100 之间。

输出

输出共一行。为姐姐的原始測试数据—— 1 到 n 的输出。

随意两个数据之间有一个空格。

例子1

输入：

4111109876532

输出：

4 1 11 10 9 8 7 6 5 3 2

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

int flag[105],ok,vist[105],len;
vector<int>loc[60];
char s[105];

void dfs(int num){
    if(num==0){
        ok=1;
        int i=0;
        do{
            printf("%c",s[i]); i++;
        }while(flag[i]==0);
        while(i<len){
            printf(" ");
            do{
                printf("%c",s[i]); i++;
            }while(flag[i]==0);
        }
        printf("
");
        return ;
    }
    for(int i=loc[num].size()-1; i>=0; i--){
        int j=loc[num][i];
        if(num<=9){
            if(vist[j]==0)
            {
                vist[j]=1;
                flag[j]=1;
                dfs(num-1);
                if(ok)return ;
                vist[j]=0;
                flag[j]=0;
            }
        }
        else if(vist[j]==0&&vist[j+1]==0)
        {
            vist[j]=vist[j+1]=1;
            flag[j]=1;
            dfs(num-1);
            if(ok)return ;
            vist[j]=vist[j+1]=0;
            flag[j]=0;
        }
    }
}

int main(){

    while(scanf("%s",s)>0){
        len=strlen(s);
        int maxnum;
        ok=0;
        memset(vist,0,sizeof(vist));
        memset(flag,0,sizeof(flag));
        flag[len]=1;
        if(len<=9)
            maxnum=len;
        else
            maxnum=(len-9)/2+9;
        for(int i=1; i<=maxnum; i++){
            loc[i].clear();
            for(int j=0; j<len; j++)
            if(i<=9){
                if(s[j]-'0'==i)
                    loc[i].push_back(j);
            }
            else if(i==(s[j]-'0')*10+s[j+1]-'0'&&j+1<len)
                loc[i].push_back(j);
        }
         dfs(maxnum);
    }
}