hdu-1515

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;
}