ABC305-F Dungeon Explore

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(Console.ReadLine());
        long N = wkArr[0];
        long M = wkArr[1];

        var VisitedSet = new HashSet<long>();
        var Stk = new Stack<long>();

        long CurrNode = 1;
        while (true) {
            VisitedSet.Add(CurrNode);
            string ReadStr = Console.ReadLine();
            if (ReadStr == "OK" || ReadStr == "-1") {
                break;
            }
            SplitAct(ReadStr);
            long[] ToNodeArr = wkArr.Skip(1).ToArray();

            bool WillContinue = false;
            foreach (long EachToNode in ToNodeArr) {
                if (VisitedSet.Add(EachToNode)) {
                    Stk.Push(CurrNode);
                    CurrNode = EachToNode;
                    WillContinue = true;
                    Console.WriteLine(EachToNode);
                    break;
                }
            }
            if (WillContinue) continue;
            long Popped = Stk.Pop();
            CurrNode = Popped;
            Console.WriteLine(Popped);
        }
    }
}

解説

HashSetで訪問ノードを管理し、
Stackで「ヘンゼルとグレーテル」のパンくずを管理し、
DFS木の探索をシュミレーションしてます。