dfs之记忆化搜索(字符串匹配，位置相对变)

题目链接:http://acm.hdu.ed

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
char a[210],b[210],c[500];
int mark[210][210];
int n;
int dfs(int i,int j,int k)
{
    if(mark[i][j])  return mark[i][j];//能够匹配
    if(c[k]=='')   return 1;
    mark[i][j]=2;//能够匹配但不存在
    if(a[i]==c[k])
        mark[i][j]=dfs(i+1,j,k+1);
    if(b[j]==c[k]&&mark[i][j]!=1)
        mark[i][j]=dfs(i,j+1,k+1);
    return mark[i][j];

}
int main()
{
    scanf("%d",&n);
    int tag=0;
    while(n--)
    {
        memset(mark,0,sizeof(mark));
        scanf("%s%s%s",a,b,c);
        int ans=dfs(0,0,0);
        if(ans==1) printf("Data set %d: yes
",++tag);
        else printf("Data set %d: no
",++tag);
    }
    return 0;
}

2016-03-2611:54:07

u.cn/showproblem.php?pid=1501