1018. 单词的划分

这辈子不可能刷oj的

include//DFS版本

using namespace std;
string s;
vector<string>restore;
int mind=10000;
bool find(string sd)
{
        for(int i=0;i<restore.size();i++){
                if(sd==restore[i]) return true;
        }
        return false;
}
void bfs(int p,int sum)
{
        //int i;
        if(p==s.size()){
                if(sum<mind) mind=sum;
        }
        else{
                for(int i=p;i<s.size();i++){
                        string str=s.substr(p,i-p+1);
                        if(find(str)){
                                int q=i+1;
                                //cout<<str<<endl;
                                bfs(q,sum+1);
                        }
                }
        }
}
int main()
{
     int t;cin>>t;
     while(t--){
             cin>>s;
             restore.clear();
             int n;cin>>n;
             for(int i=0;i<n;i++){
                     string ssd;cin>>ssd;
                     restore.push_back(ssd);
             }
             bfs(0,0);
             cout<<mind<<endl;
             mind=10000;
     }
}
你当前正在回复 博客/题目
存在问题!