HDU 1501 Zipper(DFS)

HDU 1501 Zipper(DFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1501

题意:给你3个字符串A,B和C.问你由字符串A和B的字符能否构成C字符串.你可以任意组合A和B的字符,但是A中或B中所有字符间的相对位置不能改变.且C字符的个数=A字符个数+B字符个数.

分析:

直接DFS构找出C字符即可,对于当前DFS,我们保存当前正在选取A中的第i个字符和B中的第j个字符,然后往下DFS即可.

直接DFS可能超时,因为我们会计算很多重复的情况.比如现在我们在a=2,b=2的位置(c==5),现在有两条路走,从a往下选或从b往下选,即a=5,b=2,然后到a=5,b=5. 从b往下走就是a=2,b=5到a=5,b=5.

以上注意:如果从a往下走的时候走到a=5,b=5不可行的话,那么后面一种情况从b往下走走到a=5,b=5也一定不可行.(仔细想想是不是这样)

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=205;
char A[maxn],B[maxn],C[maxn*2];  //错误1,这里C的数组是两倍长度
bool vis[maxn][maxn];            //vis数组用来标记我们之前是否考虑过a,b的情况
bool dfs(int c,int a,int b)
{
    if(C[c]==0) return true;
    if(vis[a][b]) return false;
    vis[a][b]=1;
    if(C[c]==A[a])
    {
        if(dfs(c+1,a+1,b)) return true;
    }
    if(C[c]==B[b])
    {
        if(dfs(c+1,a,b+1)) return true;
    }
    return false;
}
int main()
{
    int T; scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        memset(vis,0,sizeof(vis));
        scanf("%s%s%s",A,B,C);
        if(dfs(0,0,0)) printf("Data set %d: yes\n",kase);
        else printf("Data set %d: no\n",kase);
    }
    return 0;
}