ATC001A - 深さ優先探索

atcoder.jp

スタックを使って深さ優先探索を実装。深い=sから遠い。次に調べる区画をスタックにプッシュしていき、調べ終わったらポップして前の区画に戻る、の繰り返し。

using System;
using System.Collections.Generic;

namespace ATC001A
{
    class Program
    {
        static void Main(string[] args)
        {
            var head = Console.ReadLine().Split(' ');
            var H = int.Parse(head[0]);
            var W = int.Parse(head[1]);
            var map = new char[W, H];
            var arrived = new bool[W, H];
            var start = new Point();
            for (var y = 0; y < H; y++)
            {
                var line = Console.ReadLine();
                for (var x = 0; x < W; x++)
                {
                    map[x, y] = line[x];
                    if (line[x] == 's')
                    {
                        start = new Point(x, y);
                        arrived[x, y] = true;
                    }
                }
            }

            var answer = "No";
            var stack = new Stack<Point>();
            stack.Push(start);
            Point current;
            while (0 < stack.Count)
            {
                current = stack.Peek();
                MarkAsArrived(current);

                if (IsFence(current))
                {
                    stack.Pop();
                    continue;
                }

                if (IsGoal(current))
                {
                    answer = "Yes";
                    break;
                }

                var east = new Point(x: current.X + 1, y: current.Y);
                if (CanArrive(east))
                {
                    stack.Push(east);
                    continue;
                }

                var west = new Point(x: current.X - 1, y: current.Y);
                if (CanArrive(west))
                {
                    stack.Push(west);
                    continue;
                }

                var north = new Point(x: current.X, y: current.Y - 1);
                if (CanArrive(north))
                {
                    stack.Push(north);
                    continue;
                }

                var south = new Point(x: current.X, y: current.Y + 1);
                if (CanArrive(south))
                {
                    stack.Push(south);
                    continue;
                }

                stack.Pop();
            }

            Console.WriteLine(answer);

            bool IsFence(in Point p) => map[p.X, p.Y] == '#';

            bool IsGoal(in Point p) => map[p.X, p.Y] == 'g';

            bool CanArrive(in Point p)
            {
                if (p.X < 0) return false;
                if (p.Y < 0) return false;
                if (p.X >= W) return false;
                if (p.Y >= H) return false;
                return !arrived[p.X, p.Y];
            }

            void MarkAsArrived(in Point p) => arrived[p.X, p.Y] = true;
        }

        readonly struct Point
        {
            public Point(int x, int y)
            {
                X = x;
                Y = y;
            }

            public readonly int X;

            public readonly int Y;
        }
    }
}