牛客国庆day4 Jokewithpermutation（dfs）

链接：https://ac.nowcoder.com/acm/contest/7831/J
来源：牛客网

题目描述

Joey had saved a permutation of integers from 1 to n in a text file. All the numbers were written as decimal numbers without leading spaces.

Then Joe made a practical joke on her: he removed all the spaces in the file.

Help Joey to restore the original permutation after the Joe’s joke!

输入描述:

The input file contains a single line with a single string — the Joey’s permutation without spaces.
The Joey’s permutation had at least 1 and at most 50 numbers.

输出描述:

Write a line to the output file with the restored permutation. Don’t forget the spaces!
If there are several possible original permutations, write any one of them.

示例1

输入

4111109876532

输出

4 1 11 10 9 8 7 6 5 3 2

题意：给你一串没有空格的数字，这串数字原本是有空格的由1到n（<=50）组成的数列，现让你复原该数列。
思路：用dfs暴就可，需考虑一位数和两位数两种情况。
代码：

#include <bits/stdc++.h>

using namespace std;

char str[100];
int len, num;  // num表示数的个数及最大值
bool vis[100], tag[100], flag = false;  // tag数组记录需要输出空格的位置 

void dfs(int n) {
    if(flag) return;
    if(n > len) {
        for(int i = 1; i <= len; i++) {
            printf("%c", str[i]);
            if(tag[i] && i != len) printf(" ");
        }
        flag = true;
        return;
    }
    // 一位数，需保证下一个数不是0
    if(!vis[str[n] - '0'] && str[n] - '0' <= num && str[n+1] != '0') { 
        tag[n] = true; 
        vis[str[n] - '0'] = true;
        dfs(n+1);
        tag[n] = false;
        vis[str[n] - '0'] = false;
    }
    // 两位数，仍需保证下一个数不是0
    if(!vis[(str[n] - '0')*10 + str[n+1] - '0'] && (str[n] - '0')*10 + str[n+1] - '0' <= num && str[n+2] != '0') {
        tag[n+1] = true;
        vis[(str[n] - '0')*10 + str[n+1] - '0'] = true;
        dfs(n+2);
        tag[n+1] = false;
        vis[(str[n] - '0')*10 + str[n+1] - '0'] = false;
    }
}

int main() {
    scanf("%s", str+1);
    len = strlen(str+1);
    if(len <= 9) num = len;
    else num = (len-9)/2+9;
    memset(vis, 0, sizeof(vis));
    memset(tag, 0, sizeof(tag));
    dfs(1);
    return 0;
}