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;
}
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);
}
}
}