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 kyxyljb at 2009-08-21 16:48:19 on Problem 2192
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

char a[201],b[201],c[401];
int la,lb,lc,t[300],f[300];
bool mark,flag,used[401];

void DFS(int x,int y)  
{
    int i,j,g;
    if(y==la)
    {
        for(i=0,j=0;j<lc;j++)
            if(used[j])
            {
                if(b[i]!=c[j])
                    break;
                else
                    i++;
            }

        if(i==lb)flag=true;
        return ;
    }
    
    for(i=x;i<lc;i++)
    {
        if(a[y]==c[i]&&used[i])
        {
            used[i]=false;
            DFS(i+1,y+1);
            if(flag)
                return ;
            used[i]=true;
        }
    }
}

int main()
{
    int i,n,cas;
    cin >> n;

    for(cas=1;cas<=n;cas++)
    {
        cin >> a >> b >> c;
        la = strlen(a);
        lb = strlen(b);
        lc = strlen(c);

        if(lc!=(la + lb))
        {
           // cout << "Data set " << cas << ": no" << endl;
           printf("Data set %d: no\n",cas);
            continue;
        }

        memset(t,0,300);
        memset(f,0,300);
        mark=false;
        for(i=0;i<la;i++)t[a[i]]++;
        for(i=0;i<lb;i++)t[b[i]]++;
        for(i=0;i<lc;i++)f[c[i]]++;

        for(i=0;i<300;i++)
            if(t[i]!=f[i])
            {
                mark=true;
                break;
            }
        if(mark)
        {
            //cout << "Data set " << cas << ": no" << endl;
            printf("Data set %d: no\n",cas);
            continue;
        }

        memset(used,true,401);
        flag = false;
     /*   for(i=0;i<lc-lb;i++)
        {
            DFS(i,0);
            if(flag)break;
        } */
        DFS(0,0);
        if(flag)
            //cout << "Data set " << cas << ": yes" << endl;
            printf("Data set %d: yes\n",cas);
        else
            //cout << "Data set " << cas << ": no" << endl;
            printf("Data set %d: no\n",cas);
    }
    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