3

我正在为一些高中生写一个游戏来学习一般的计算机科学/数学。

但我也陷入了我为自己设计的一个问题，想看看是否有更有效的方法来解决它。

问题：

给出一个单词“Abc”和一个单词列表 [“Cat”, “Tick”, “Apple”, “Orange”, ... ] 是否可以在第一个单词的最后一个字符的情况下构建一个单词链与从单词列表中选择的任何单词的第一个字符相同。而这个链可以通过给定的词表成功构建吗？如果可能返回真，否则返回假。

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

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

例如，

案例 #1： 将 Return"Abc", ["Girl", "King", "Cat", "Dog", "Good", "Tick"] 设为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 回答