一道搜索题，不过用了一个visit数组比较重要~~值得学习！！
题目大意：给3个字符串，问第三个串能不能由前两个构成，在不改变相互顺序的情况下！
visit标记数组很重要，去掉must超时~~
直接贴代码，代码很精简：
View Code 1 # include
2 # include 3 char str1[205],str2[205],str[405],flag,visit[205][205]; 4 void dfs(int i,int j,int k) 5 { 6 if(str[i]==0 && str1[j]==0 && str2[k]==0) {flag=1;return;} 7 if(str[i]!=str1[j] && str[i]!=str2[k]) return; 8 if(visit[j][k]) return;///如果该状态已经访问过了，那就无需再访问了 9 visit[j][k]=1;
10 if(str[i]==str1[j]) dfs(i+1,j+1,k);
11 if(flag) return;
12 if(str[i]==str2[k]) dfs(i+1,j,k+1);
13 }
14 int main()
15 {
16 int t,ncase;
17 scanf("%d",&ncase);
18 for(t=1;t<=ncase;t++)
19 {
20 scanf("%s%s%s",str1,str2,str);
21 memset(visit,0,sizeof(visit));
22 flag=0;
23 dfs(0,0,0);
24 printf("Data set %d: ",t);
25 if(flag) printf("yes\n");
26 else printf("no\n");
27 }
28 return 0;
29 }
Tags:
延伸阅读
最新评论