【HDOJ】1501 Zipper

DFS。注意剪枝,0ms。

 #include <stdio.h>
#include <string.h> #define False 0
#define True 1
#define MAXN 201 char stra[MAXN], strb[MAXN], strc[MAXN<<];
int len1, len2, len3; int dfs(int e1, int e2, int e3) {
int i, flg = False; if (e1+e2+ != e3) // 剩余长度必须相等
return False; if (e3 == -)
return True; for (i=e1; i>=e3-e2-; --i)  // 控制循环条件
if (stra[i] == strc[e3]) {
flg = dfs(i-, e2, e3-);
break;
} if (flg) return True; for (i=e2; i>=e3-e1-; --i)  // 控制循环条件
if (strb[i] == strc[e3]) {
return dfs(e1, i-, e3-);
break;
} return False;
} int main() {
int case_n;
int i; scanf("%d", &case_n); for (i=; i<=case_n; ++i) {
scanf("%s %s %s", stra, strb, strc);
len1 = strlen(stra);
len2 = strlen(strb);
len3 = strlen(strc);
printf("Data set %d: ", i);
if (len3 != len1+len2)
printf("no\n");
else {
if ( dfs(len1-, len2-, len3-) )
printf("yes\n");
else
printf("no\n");
}
} return ;
}
上一篇:nginx字体文件配置


下一篇:IO(七)----转换流