hdu-1515

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/41787843

dfs

题意：给你两个字符串，问：第一个字符串按入栈出栈规则，能否达到第二个字符串，输出所有的方法，i表示入栈，o表示出栈。

用dfs模拟第一个字符串入栈出栈过程:

1. 当前字符入栈，就向下一层递归，即搜向下一个字符

2. 栈顶元素出栈，对新的栈顶元素判断

注意回溯的条件

#include<stdio.h>    
#include<iostream>    
#include<math.h>    
#include<stdlib.h>    
#include<ctype.h>    
#include<algorithm>    
#include<vector>    
#include<string.h>    
#include<queue>    
#include<stack>    
#include<set>    
#include<map>    
#include<sstream>    
#include<time.h>    
#include<utility>    
#include<malloc.h>    
#include<stdexcept>    

using namespace std;

char a[1000], b[1000];
char str1[1000], str2[1000];
char ans[1000];

stack<char> q;

int l1,l2;

void dfs(int cur1,int cur2,int k)
{
    if (cur2 == l1)
    {
        for(int i=0;i < k;i++)
        {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
        return ;
    }

    if (cur1 < l1)
    {
        ans[k] = 'i';
        q.push(a[cur1]);
        dfs (cur1+1,cur2,k+1);
        q.pop();
    }

    if (!q.empty() && q.top() == b[cur2])
    {
        ans[k] = 'o';
        char c = q.top();
        q.pop();
        dfs(cur1,cur2+1,k+1);
        q.push( c );
    }
}

int main()
{
    while (scanf("%s %s",a,b)!=EOF)
    {
        while (!q.empty())
        {
            q.pop();
        }
        int ok = 1;

        l1 = strlen(a);
        l2 = strlen(b);

        if (l1 != l2)
        {
            ok = 0;
        }

        strcpy(str1,a);
        strcpy(str2,b);

        sort(str1, str1 + l1);
        sort(str2, str2 + l2);

        if (strcmp(str1, str2) != 0)
            ok = 0;
        if (!ok)
        {
            printf("[\n]\n");
        }
        else
        {
            printf("[\n");

            dfs(0,0,0);

            printf("]\n");
        }
    }
    return 0;
}