HDU 1501 Zipper（Dfs记忆化搜索）

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

 

题意：前两个字符串能和能合成第三个字符串，字符串内相对顺序不变

 

开始用Dfs()以为用了变量标记如果失败不停的return。。。。然后超时，然后想不通为什么要用vis[i][j]来标记有没访问过该状态，我当时想Dfs(i,j,k)里面都一直在递增啊，而且如果失败了回溯的时候就return了，怎么还会遇到该状态呢。。。。。。原来如果在递归的第一个Dfs()匹配成功，回溯后（i,j,k就隐式地减少了），而且遇到flag也不会return（因为flag是失败才return的），然后进了第二个Dfs（）。。。。如果没有vis[i][j]的话，就会在里面浪费时间了。。。。。。。所以vis[i][j]是不管你成功还是失败，只要以前有过这个状态就会return

 

先发错误代码：

#include <iostream>
using namespace std;

const int M = 555;

char c1[M], c2[M], c3[M];
int l1, l2, l3;
int flag;

bool Dfs(int i, int j, int k)
{
if (flag == 0)
    {
return 0;
    }

if (c1[i] != c3[k] && c2[j] != c3[k])
    {
        flag = 0;//这里也是错的，这个条件不一定就匹配不了。。。因为还有剩余的没搜
return 0;//这题我们应该是在所有的情况里找到能匹配的话就标记flag = 1，即求是否存在可以匹配的情况
    }

if (k == l3)
    {
return 1;
    }

if (c1[i] == c3[k] && i + 1 < l1)
    {
        Dfs(i + 1, j, k + 1);
if (flag == 0)//匹配成功在这里就不会return，再进下面的Dfs（）就会有重复的状态了
        {
return 0;
        }
    }

if (c2[j] == c3[k] && j + 1 < l2)
    {
        Dfs(i, j + 1, k  + 1);
if (flag == 0)
        {
return 0;
        }
    }
if (flag)
    {
return 1;
    }
else
    {
return 0;
    }
}


int main()
{
int t;
    scanf("%d", &t);
int case1 = 0;
while (t--)
    {
        scanf("%s%s%s", c1, c2, c3);
        l1 = strlen(c1);
        l2 = strlen(c2);
        l3 = strlen(c3);
        flag = 1;

if (l1 + l2 != l3)
        {
            flag = 0;
        }
        printf("Date set %d: %s\n", ++case1, Dfs(0, 0, 0) ? "yes" : "no");
    }
return 0;
}

 

 

 

AC代码：

#include <iostream>
using namespace std;

const int M = 555;

char c1[M], c2[M], c3[M];
int l1, l2, l3;
int flag;
bool vis[M][M];

void Dfs(int i, int j, int k)
{

if (vis[i][j])
    {
return ;
    }

    vis[i][j] = 1;

if (k == l3)
    {
        flag = 1;
return ;
    }

if (c1[i] != c3[k] && c2[j] != c3[k])
    {
return ;
    }



if (c1[i] == c3[k] && i + 1 <= l1)
    {
        Dfs(i + 1, j, k + 1);

    }

if (c2[j] == c3[k] && j + 1 <= l2)
    {
        Dfs(i, j + 1, k  + 1);
    }

}


int main()
{
int t;
    scanf("%d", &t);
int case1 = 0;
while (t--)
    {
        scanf("%s%s%s", c1, c2, c3);
        l1 = strlen(c1);
        l2 = strlen(c2);
        l3 = strlen(c3);
        flag = 0;

if (l1 + l2 != l3)
        {
            flag = 0;
            printf("Data set %d: %s\n", ++case1, flag ? "yes" : "no");
continue;
        }
        memset(vis, 0, sizeof(vis));
        Dfs(0, 0, 0);
        printf("Data set %d: %s\n", ++case1, flag ? "yes" : "no");
    }
return 0;
}