ARC031B - 埋め立て

atcoder.jp

埋め立て候補の海をスタート地点にした、スタックを使った深さ優先探索。探索終了してスタート地点に戻ったとき、全ての陸地を訪れていれば1つの島にできる。

using System;
using System.Collections.Generic;

namespace ARC031B
{
    class Program
    {
        static void Main(string[] args)
        {
            var map = new char[10, 10];
            var landCount = 0;
            for (var y = 0; y < 10; y++)
            {
                var line = Console.ReadLine();
                for (var x = 0; x < 10; x++)
                {
                    var c = line[x];
                    map[x, y] = c;
                    if (c == 'o')
                    {
                        landCount++;
                    }
                }
            }

            for (var y = 0; y < 10; y++)
            {
                for (var x = 0; x < 10; x++)
                {
                    if (map[x, y] == 'o')
                    {
                        continue;
                    }

                    var start = (x, y);
                    var arrived = new bool[10, 10];
                    var count = 0;
                    var stack = new Stack<(int x, int y)>();
                    stack.Push(start);
                    while (stack.Count > 0)
                    {
                        var current = stack.Peek();
                        if (!arrived[current.x, current.y])
                        {
                            arrived[current.x, current.y] = true;
                            if (map[current.x, current.y] == 'o')
                            {
                                count++;
                            }
                        }

                        var next = (x: current.x + 1, y: current.y);
                        if (next.x < 10 && !arrived[next.x, next.y] && map[next.x, next.y] == 'o')
                        {
                            stack.Push(next);
                            continue;
                        }

                        next = (x: current.x - 1, y: current.y);
                        if (next.x >= 0 && !arrived[next.x, next.y] && map[next.x, next.y] == 'o')
                        {
                            stack.Push(next);
                            continue;
                        }

                        next = (x: current.x, y: current.y - 1);
                        if (next.y >= 0 && !arrived[next.x, next.y] && map[next.x, next.y] == 'o')
                        {
                            stack.Push(next);
                            continue;
                        }

                        next = (x: current.x, y: current.y + 1);
                        if (next.y < 10 && !arrived[next.x, next.y] && map[next.x, next.y] == 'o')
                        {
                            stack.Push(next);
                            continue;
                        }

                        stack.Pop();
                    }

                    if (count == landCount)
                    {
                        Console.WriteLine("YES");
                        return;
                    }
                }
            }

            Console.WriteLine("NO");
        }
    }
}