HNU Joke with permutation （深搜dfs）

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=13341&courseid=0

Joke with permutation

Time Limit: 3000ms, Special Time Limit:7500ms, Memory Limit:65536KB

Total submit users: 85, Accepted users: 57

Problem 13341 : Special judge

Problem description

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!

Input

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.

Output

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.

Sample Input

4111109876532

Sample Output

4 1 11 10 9 8 7 6 5 3 2

Problem Source

NEERC 2014

Submit   Discuss   Judge Status  Problems  Ranklist

题目大意：将一串完整的字符串分成1~n个数。将空格补进去，并将其输出。

解题思路：1、注意这个n是可以求出来的

　　　　　2、一个数字一个数字比较，只要满足这个数字小于n，还有保证这个数字没有访问过就ok啦

　　　

详见代码。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int n,flag;

 char ch[];

 int ans[];

 bool vis[];

 bool dfs(int i,int k)

 {

     if (flag==)

         return true;

     if (k==n+)

     {

         for (int i=;i<k-;i++)

         {

             printf ("%d ",ans[i]);

         }

         printf ("%d\n",ans[k-]);

         flag=;

         return true;

     }

     if (ch[i]-''<=n&&!vis[ch[i]-'']&&ch[i]-''>)

     {

         ans[k]=ch[i]-'';

         vis[ch[i]-'']=;

         if(dfs(i+,k+)) return true;

         vis[ch[i]-'']=;

     }

     if ((ch[i]-'')*+ch[i+]-''<=n&&(ch[i]-'')*+ch[i+]-''>&&!vis[(ch[i]-'')*+ch[i+]-''])

     {

         ans[k]=(ch[i]-'')*+ch[i+]-'';

         vis[(ch[i]-'')*+ch[i+]-'']=;

         if(dfs(i+,k+)) return true;

         vis[(ch[i]-'')*+ch[i+]-'']=;

     }

     return false;

 }

 int main()

 {

     while (scanf("%s",ch)!=EOF)

     {

         flag=;

         memset(ans,,sizeof(ans));

         memset(vis,,sizeof(vis));

         int len=strlen(ch);

         if (len>)

             n=(len-)/+;

         else

             n=len;

         dfs(,);//dfs();

     }

     return ;

 }