Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dfs加减枝

Posted by zpdlut at 2010-09-08 10:26:24 on Problem 2192
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator