zoj 1004 dfs

  想多了！以为一直dfs所有的情况会超时，所以直接忽略了，就自己想了一个优化的算法，最后测试结果对了，但是wa了，自己写算法很容易考虑不周的，还是在最后没有办法的时候在考虑自己的算法吧！！！简单的dfs就可以了！

#include<stdio.h>
#include<string.h>
#define Max 100

char goal_str[Max];
char source_str[Max];
char stack[Max];
int path[Max];
int lenth,top,pointer;

void print_path(void)
{
	int i;
	for(i=0;i<2*lenth;i++)
	{
		if(path[i]==1)
			printf("i ");
		else
			printf("o ");
	}
	printf("
");
}
void dfs(int npush,int npop)
{
	char tmp;
	if(npush==lenth&&npop==lenth)
	{
		print_path();
		return ;
	}
	if(npush<lenth)
	{
		path[pointer++]=1;
		stack[top++]=source_str[npush];
		dfs(npush+1,npop);
		top--;
		pointer--;
	}
	if(top>0&&stack[top-1]==goal_str[npop])
	{
		tmp=stack[top-1];
		path[pointer++]=-1;
		top--;
		dfs(npush,npop+1);
		pointer--;
		top++;
		stack[top-1]=tmp;
	}
}
int main()
{
	int n1;
	while(scanf("%s%s",source_str,goal_str)!=EOF)
	{
		pointer=0;
		top=0;
		
		printf("[
");
		
		lenth=strlen(source_str);
		n1=strlen(goal_str);
		
		if(n1==lenth)
			dfs(0,0);
			
		printf("]
");

	}
	return 0;
}