Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
dfs加减枝#include<iostream> #include<string> using namespace std; string s1,s2,s3; int num1,num2,num3; int dfs(int len1,int len2,int len3) { if(len1==num1&&len2==num2) return 1; if(len1<num1&&s1[len1]==s3[len3]) if(dfs(len1+1,len2,len3+1)) return 1; if(len2<num2&&s2[len2]==s3[len3]) if(dfs(len1,len2+1,len3+1)) return 1; return 0; } int main() { int nums; cin>>nums; for(int i=0;i<nums;i++) { cin>>s1>>s2>>s3; num1 = s1.size(); num2 = s2.size(); num3 = s3.size(); if(num1+num2!=num3||(s1[num1-1]!=s3[num3-1]&&s2[num2-1]!=s3[num3-1])) { cout<<"Data set "<<i+1<<": no"<<endl; continue; } if(dfs(0,0,0)) cout<<"Data set "<<i+1<<": yes"<<endl; else cout<<"Data set "<<i+1<<": no"<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator