HDU1501 Zipper(DFS)

题目链接

题意:给出三个字符串s1,s2,s,其中s1和s2的长度和等于s的长度和,不可以改变1,2两串内字母顺序,将二者混合问能否形成s。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
char s1[205], s2[205];
char s[405];
int vis[300][300];
int flag;
void dfs(int a, int b, int c){
    if(vis[a][b]) return;
    vis[a][b] = 1;
    if(s == '\0'){
        flag = 1;
        return;
    }
    if(s1[a] == s && s2[b] == s){
        dfs(a+1, b, c+1);
        dfs(a, b+1, c+1);
    }else if(s1[a] == s){
        dfs(a+1, b, c+1);
    }else if(s2[b] == s){
        dfs(a, b+1, c+1);
    }
}

int main(){
    //freopen("a.txt", "r", stdin);
    int n; cin >> n;
    for(int cas = 1; cas <= n; cas++){
        memset(vis, 0, sizeof(vis));
        flag = 0;
        scanf("%s %s %s", s1, s2, s);
        dfs(0, 0, 0);
        char ans[5] = "no";
        //cout << flag << endl;
        if(flag) strcpy(ans, "yes");
        printf("Data set %d: %s\n", cas, ans);
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with DFS