Q14 W杯出場国しりとり

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyouraiDef
    {
        internal int Level;
        internal List<string> UsedList;
    }

    static void Main()
    {
        var CountryList = new List<string>();
        CountryList.AddRange(new string[] { "Brazil", "Croatia", "Mexico" });
        CountryList.AddRange(new string[] { "Cameroon", "Spain", "Netherlands" });
        CountryList.AddRange(new string[] { "Chile", "Australia", "Colombia" });
        CountryList.AddRange(new string[] { "Greece", "Cote d'lvoire", "Japan" });
        CountryList.AddRange(new string[] { "Uruguay", "Costa Rica", "England" });
        CountryList.AddRange(new string[] { "Italy", "Switzerland", "Ecuador" });
        CountryList.AddRange(new string[] { "France", "Honduras", "Argentina" });
        CountryList.AddRange(new string[] { "Bosnia and Herzegovina", "Iran", "Nigeria" });
        CountryList.AddRange(new string[] { "Germany", "Portugal", "Ghana" });
        CountryList.AddRange(new string[] { "USA", "Belgium", "Algeria" });
        CountryList.AddRange(new string[] { "Russia", "Korea Republic" });
        CountryList.Sort();
        string[] CountryArr = CountryList.ToArray();

        var stk = new Stack<JyouraiDef>();
        JyouraiDef WillPush;
        WillPush.Level = 0;
        WillPush.UsedList = new List<string>();
        stk.Push(WillPush);

        int AnswerLength = 0;
        while (stk.Count > 0) {
            JyouraiDef Popped = stk.Pop();

            if (AnswerLength < Popped.Level) {
                AnswerLength = Popped.Level;
                Console.WriteLine("長さ{0}の解候補を発見", AnswerLength);
                Popped.UsedList.ForEach(X => Console.Write("{0},", X));
                Console.WriteLine();
            }

            foreach (string EachCountry in CountryArr) {
                //再使用は不可
                if (Popped.UsedList.Contains(EachCountry)) continue;

                //カレントの国名の末尾と、次の国名の先頭が、一致すること
                if (Popped.Level > 0) {
                    string CurrStr = Popped.UsedList[Popped.Level - 1];
                    string CurrLast = CurrStr.Substring(CurrStr.Length - 1).ToUpper();

                    string CountryFirst = EachCountry.Substring(0, 1).ToUpper();

                    if (CurrLast != CountryFirst) continue;
                }
                WillPush.Level = Popped.Level + 1;
                WillPush.UsedList = new List<string>(Popped.UsedList) { EachCountry };
                stk.Push(WillPush);
            }
        }
        Console.WriteLine("解は{0}", AnswerLength);
    }
}

実行結果

長さ1の解候補を発見
USA,
長さ2の解候補を発見
USA,Australia,
長さ3の解候補を発見
USA,Australia,Argentina,
長さ4の解候補を発見
USA,Australia,Argentina,Algeria,
長さ5の解候補を発見
Spain,Nigeria,Australia,Argentina,Algeria,
長さ6の解候補を発見
Netherlands,Spain,Nigeria,Australia,Argentina,Algeria,
長さ7の解候補を発見
Korea Republic,Cote d'lvoire,Ecuador,Russia,Australia,Argentina,Algeria,
長さ8の解候補を発見
Korea Republic,Cameroon,Netherlands,Spain,Nigeria,Australia,Argentina,Algeria,
解は8

解説

深さ優先探索でナイーブに解いてます。