最短経路探索

Program.cs

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

namespace ProgrammingContestChallenge.Maze
{
    class FootPrint
    {
        public FootPrint(int x, int y, FootPrint prev)
        {
            X = x;
            Y = y;
            Prev = prev;
        }

        public int X;
        public int Y;
        public FootPrint Prev;
    }

    static class Program
    {
        private const char Wall = '#';
        private const char Start = 'S';
        private const char Goal = 'G';
        private const char AlreadyPassed = '@';

        private const string Maze = @"
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
";

        static void Main(string[] args)
        {
            var result = Solve(Convert(Maze));
            var map = Convert(Maze);
            int turn = 0;
            while(result != null)
            {
                map[result.Y][result.X] = AlreadyPassed;
                result = result.Prev;
                turn++;
            }
            Console.WriteLine("turn: " + turn.ToString());
            var s = string.Join("\r\n", map.Select(x => new string(x)));
            Console.WriteLine(s);
        }

        static char[][] Convert(string mazeMap)
        {
            return mazeMap.Split(new string[] { "\r", "\n" }, StringSplitOptions.RemoveEmptyEntries).Select(x => x.ToCharArray()).ToArray();
        }

        static FootPrint Solve(char[][] map)
        {
            var branch = new Queue<FootPrint>();
            for (int h = 0; h < map.Length && !branch.Any(); h++)
            {
                int w = 0;
                foreach (var i in map[h])
                {
                    if (i == Start)
                    {
                        branch.Enqueue(new FootPrint(w, h, null));
                        break;
                    }
                    w++;
                }
            }

            return branch.ToEnumerable()
                         .Where(x => x.Y > -1
                                     && x.Y < map.Length
                                     && x.X > -1
                                     && x.X < map[x.Y].Length
                                     && map[x.Y][x.X] != Wall
                                     && map[x.Y][x.X] != AlreadyPassed)
                         .Select(
                             x =>
                                 {
                                     if (map[x.Y][x.X] != Goal)
                                     {
                                         map[x.Y][x.X] = AlreadyPassed;
                                     }
                                     branch.Enqueue(new FootPrint(x.X, x.Y - 1, x));
                                     branch.Enqueue(new FootPrint(x.X, x.Y + 1, x));
                                     branch.Enqueue(new FootPrint(x.X - 1, x.Y, x));
                                     branch.Enqueue(new FootPrint(x.X + 1, x.Y, x));
                                     return x;
                                 })
                         .FirstOrDefault(x => map[x.Y][x.X] == Goal);
        }

        static IEnumerable<T> ToEnumerable<T>(this Queue<T> q)
        {
            while (q.Count > 0)
            {
                yield return q.Dequeue();
            }
        }
    }
}