ARC005C - 器物損壊！高橋君

atcoder.jp

今までの幅優先探索ではスタート地点からの距離をカウントしていたけど、今回はその区画に着くまでに最低何回塀を壊す必要があるかをカウントしてみた。

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

namespace ARC005C
{
    class Program
    {
        static void Main(string[] args)
        {
            var HW = Console.ReadLine().Split(' ');
            var H = int.Parse(HW[0]);
            var W = int.Parse(HW[1]);
            (int x, int y) start = default;
            (int x, int y) goal = default;
            var map = new char[H, W];
            var broke = new int[H, W];
            for (var y = 0; y < H; y++)
            {
                var row = Console.ReadLine().ToList();
                for (var x = 0; x < row.Count; x++)
                {
                    map[y, x] = row[x];
                    broke[y, x] = int.MaxValue;
                    if (row[x] == 's')
                    {
                        start = (x, y);
                    }
                    else if (row[x] == 'g')
                    {
                        goal = (x, y);
                    }
                }
            }

            var queue = new Queue<(int x, int y, int c)>();
            queue.Enqueue((start.x, start.y, 0));
            broke[start.y, start.x] = 0;
            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                foreach (var next in GetNexts((current.x, current.y)))
                {
                    // マップの外だったらスキップ
                    if (next.x < 0 ||
                        next.y < 0 ||
                        next.x >= W ||
                        next.y >= H)
                    {
                        continue;
                    }

                    // 塀だった場合、壊した回数が2回未満なら、壊して探索続行
                    if (map[next.y, next.x] == '#' && current.c < 2)
                    {
                        broke[next.y, next.x] = Math.Min(
                            broke[next.y, next.x],
                            current.c + 1);
                        queue.Enqueue((next.x, next.y, current.c + 1));
                        continue;
                    }

                    // 塀以外だった場合で、まだ訪れていないか、
                    // 現在よりも多く壁を壊して訪れていたら、探索続行
                    if (map[next.y, next.x] != '#' && broke[next.y, next.x] > current.c)
                    {
                        broke[next.y, next.x] = Math.Min(
                            broke[next.y, next.x],
                            current.c);
                        queue.Enqueue((next.x, next.y, current.c));
                        continue;
                    }
                }
            }

            var answer = broke[goal.y, goal.x] <= 2 ? "YES" : "NO";
            Console.WriteLine(answer);
        }

        static IEnumerable<(int x, int y)> GetNexts((int x, int y) p)
        {
            yield return (p.x - 1, p.y);
            yield return (p.x + 1, p.y);
            yield return (p.x, p.y - 1);
            yield return (p.x, p.y + 1);
        }
    }
}