4
HDU1501 Zipper（DFS）
source link: https://arminli.com/hdu1501/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU1501 Zipper（DFS）
March 19, 2016
题意：给出三个字符串 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;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK