■http://anond.hatelabo.jp/20100113192313

これで40分。

タイムアタックってことでアルゴリズムは全幅探索で書き上げました。

エラーチェック皆無。

A*ならもう5分ほど延びるかな？

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

namespace Maze
{
    class Program
    {
        // 探索用地図
        static int[,] maze;

        // 始点終点
        static Position Start = new Position(0, 0), Goal = new Position(0, 0);

        static void Main(string[] args)
        {
            //////////////////////////// まずは各行のリストとして読み込み
            string[] inMaze;

            using (var fp = new FileStream(args[0], FileMode.Open, FileAccess.Read))
            using (var iStream = new StreamReader(fp))
                inMaze = iStream.ReadToEnd().Split('\n');

            // 迷路幅
            int height = inMaze.Length;

            // 迷路高さ
            int width = inMaze[0].Length;

            /////////////////////////// 読み込んだ迷路を作業用地図に展開
            maze = new int[width, height];
            for (int y = 0; y < height; ++y)
            {
                string line = inMaze[y];
                for (int x = 0; x < line.Length; ++x)
                {
                    maze[x, y] = line[x] == '*'
                        ? -1
                        : 0;
                    if (line[x] == 'S') Start = new Position(x, y);
                    if (line[x] == 'G') Goal = new Position(x, y);
                }
            }

            // 探索実行
            int dist = Search(maze, Start);

            // 探索結果から最短経路を再現
            Position backTracer = Goal;
            while (dist&gt;1){
                --dist;
                backTracer = backTracer.Nearbys.First(pos =&gt; maze[pos.X,pos.Y] == dist);
                maze[backTracer.X, backTracer.Y] = -2;
            }

            //////////////////// 最短経路こみのアスキー地図に変換
            char[,] outMaze = new char[width, height];

            for (int y = 0; y < height; ++y)
            {
                for (int x = 0; x < width; ++x)
                {
                    outMaze[x, y] = maze[x, y] == -2
                        ? '$'
                        : maze[x, y] == -1
                            ? '*'
                            : ' ';
                }
            }
            outMaze[Start.X, Start.Y] = 'S';
            outMaze[Goal.X, Goal.Y] = 'G';


            ////////////////////// 結果は標準出力に。
            for (int y = 0; y < height; ++y)
            {
                for (int x = 0; x < width; ++x)
                    Console.Write(outMaze[x, y]);
                Console.WriteLine();
            }
            Console.ReadLine();
        }

        /// <summary&gt;
        /// 探索する。SG間の道のりを返す（道のり＝SGが隣接しているなら1）
        /// </summary&gt;
        private static int Search(int[,] maze, Position Start)
        {
            List<Position&gt; FrontLine = new List<Position&gt;();
            FrontLine.Add(Start);
            int dist = 1;
            for (; ; )
            {
                List<Position&gt; NextFrontLine = new List<Position&gt;();
                foreach (var pos in FrontLine)
                {
                    foreach (var nextPos in pos.Nearbys)
                    {
                        if (nextPos == Goal) return dist;
                        if (maze[nextPos.X, nextPos.Y] == 0)
                        {
                            maze[nextPos.X, nextPos.Y] = dist;
                            NextFrontLine.Add(nextPos);
                        }
                    }
                }
                FrontLine = NextFrontLine;
                ++dist;
            }
        }
    }

    struct Position
    {
        public readonly int X, Y;
        public Position(int x, int y) { X = x; Y = y; }

        public IEnumerable<Position&gt; Nearbys
        {
            get
            {
                return new[]{
                    new Position(X-1,Y),
                    new Position(X,Y-1),
                    new Position(X+1,Y),
                    new Position(X,Y+1),
                };
            }
        }

        public static bool operator==(Position p1, Position p2){
            return p1.X == p2.X &amp;&amp; p1.Y == p2.Y;
        }

        public static bool operator!=(Position p1, Position p2){
            return p1.X != p2.X || p1.Y != p2.Y;
        }
    }
}

Permalink | 記事への反応(2) | 02:18

ツイートシェア