ZOJ1004 DFS基础

这道题一看就觉得是DFS，但是，不对，还有栈，这就有点难办了。
DFS+栈一波新姿势。
在DFS里面用栈的思想。
DFS主要就是搜下去，
然后前一个状态标记，搜完以后，还是要保持前一个状态。
然后就把栈往上面一套就好了。
进栈出栈用数组分别标记一下就好了。
一个是出栈，也就是要被进栈的字符串的长度sum

#include<iostream>
#include<cstdio>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 210

char s1[1010];
char s2[1010];
int d[1010];
char pa[1010];
int lenth;
int pp,tt;

void dfs(int sum,int num)
{
    if(sum==lenth&&num==lenth)
    {
        for(int i=0;i<(2*lenth);i++)
        {
            if(d[i]==1)
                printf("i ");
            else
                printf("o ");
        }
        printf("
");
    }
    if(sum<lenth)
    {
        d[pp++]=1;
        pa[tt++]=s1[sum];
        dfs(sum+1,num);
        tt--;
        pp--;
    }
    char k;
    if(tt>0&&pa[tt-1]==s2[num])
    {
        d[pp++]=-1;
        k=pa[tt-1];
        tt--;
        dfs(sum,num+1);
        pp--;
        tt++;
        pa[tt-1]=k;
    }
}


int main()
{
    while(~scanf("%s%s",s1,s2))
    {
        int len1,len2;
        len1=strlen(s1);
        len2=strlen(s2);
        printf("[
");
        if(len1!=len2)
        {
            printf("]
");
            continue;
        }
        lenth=len1;
        dfs(0,0);
        printf("]
");
    }
    return 0;
}