ABC007C - 幅優先探索

atcoder.jp

キューを使って幅優先探索を実装した。探索でスタート地点からの距離を記録していき、探索し終わったらゴール地点までの距離を出力。

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

namespace ABC007C
{
    class Program
    {
        static void Main(string[] args)
        {
            var RC = Console.ReadLine().Split(' ');
            var R = int.Parse(RC[0]);
            var C = int.Parse(RC[1]);
            var s = Console.ReadLine().Split(' ');
            var sy = int.Parse(s[0]) - 1;
            var sx = int.Parse(s[1]) - 1;
            var g = Console.ReadLine().Split(' ');
            var gy = int.Parse(g[0]) - 1;
            var gx = int.Parse(g[1]) - 1;
            var maze = new List<string>();
            var dist = new List<List<int>>();
            for (var i = 0; i < R; i++)
            {
                var c = Console.ReadLine();
                maze.Add(c);
                dist.Add(Enumerable.Repeat(-1, C).ToList());
            }

            var queue = new Queue<(int x, int y)>();
            queue.Enqueue((sx, sy));
            dist[sy][sx] = 0;
            while (queue.Count > 0)
            {
                var current = queue.Dequeue();

                foreach (var next in GetNext(current))
                {
                    if (next.x < 0 ||
                        next.y < 0 ||
                        next.x >= C ||
                        next.y >= R ||
                        dist[next.y][next.x] != -1 ||
                        maze[next.y][next.x] == '#')
                    {
                        continue;
                    }

                    dist[next.y][next.x] = dist[current.y][current.x] + 1;
                    queue.Enqueue(next);
                }
            }

            var answer = dist[gy][gx];
            Console.WriteLine(answer);
        }

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