3

高校生がコンピュータ サイエンスや数学全般について学ぶためのゲームを書いています。

しかし、私は自分のために設計した質問にも行き詰まっており、それを解決するためのより効率的な方法があるかどうかを確認したいと考えています.

質問：

単語 "Abc" と単語のリスト ["Cat", "Tick", "Apple", "Orange", ... ] を与えると、最初の単語の最後の文字が次のような条件で単語チェーンを構築できますか?単語リストから選択した単語の最初の文字と同じです。そして、このチェーンは、与えられた単語リストによってうまく構築できるでしょうか? 可能な場合は true、そうでない場合は false を返します。

INPUT: boolean lastCharPermutation(String startingWord, String [] wordsList) { .. }

OUTPUT: true for able to complete the combination, false otherwise

例えば、

ケース #1:"Abc", ["Girl", "King", "Cat", "Dog", "Good", "Tick"] Return true を取る理由Abc-Cat-Tick-King-Good-Dog-Girl

ケース #2:ここで停止するため、 "Abc", ["Tour", "Game", "Cat", "Bridge", "Women", "Man"] Return false を使用するAbc-Cat-Tour

4

1 に答える 1

1

あなたがやりたいのはオイラーパスです..私はCodechefで同じ問題を解決しました。使用したい場合は、これが私のコードです。説明が必要な場合は教えてください。非常に理解しやすいですが。

#include <iostream>
#include <string.h>
#include <string>
using namespace std;

int visit[26];
int adj[26][26];
int count=0;

void scc(int i) //Strongly COnnected Component
{
    visit[i]=-1;//visiting
    for(int t=0;t<26;t++)
    {
        if(adj[i][t]>0 && visit[t]==0)//not visited yet
        scc(t);
    }
    visit[i]=1;
    count++;
}

int main()
{
    string in;
    int t,n,k,nv,counta,countb,flag;
    int a[26],b[26];
    cin >> t;
    while(t--)
    {
        cin >> n;
        memset(a,0,26*sizeof(int));
        memset(b,0,26*sizeof(int));
        memset(visit,0,26*sizeof(int));
        memset(adj,0,26*26*sizeof(int));
        k=26;count=0;counta=0;countb=0;flag=0;nv=0;

        while(n > 0)
        {
            n--;
            cin >> in;
            a[in[0]-'a']++;
            b[in[in.size()-1]-'a']++;
            adj[in[0]-'a'][in[in.size()-1]-'a'] = 1;
            adj[in[in.size()-1]-'a'][in[0]-'a'] = 1;
        }

        for(int i=0;i<26;i++)
            if(a[i]>0)
            {
                scc(i);
                break;
            }

        for(int i=0;i<26;i++)
            if(a[i]!=0 || b[i]!=0)
                nv++;

        if(count!=nv)
            flag=1;     

        while(k > 0 && flag!=1  )
        {
            if(a[k-1]-b[k-1] == 1)
                counta++;
            else if(b[k-1]-a[k-1] == 1)
                countb++;
            else if(a[k-1]!=b[k-1])
                flag = 1;
            k--;
        }

        if(flag==0 && counta==countb && ( counta==1 || counta ==0))
            cout << "Ordering is possible." <<endl;
        else
            cout << "The door cannot be opened." <<endl;
    }

    return 0;
}
于 2013-06-11T05:19:44.957 に答える