| ||||||||||
| 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