■人材獲得作戦・４　試験問題ほか

http://okajima.air-nifty.com/b/2010/01/post-abc6.html

迷路の最短経路を求める問題が出たので解いてみた

幅優先探索を使えばいいのがわかっていたのですんなりかけたのだが、無限ループになる個所があったので動くようになるまで時間がかかった

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

namespace MazeFind
{
    class Point
    {
        public int x;
        public int y;
        public Point before;
        public Point(int x, int y,Point before)
        {
            this.x = x;
            this.y = y;
            this.before = before;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            const char BreakChar = 'B';
            const char GoalChar = 'G';
            const char WallChar = '*';
            const char BeforeChar = '.';

            StringBuilder[] maze = new StringBuilder[]{
                new StringBuilder("**************************"),
                new StringBuilder("*S* *                    *"),
                new StringBuilder("* * *  *  *************  *"),
                new StringBuilder("* *   *    ************  *"),
                new StringBuilder("*    *                   *"),
                new StringBuilder("************** ***********"),
                new StringBuilder("*                        *"),
                new StringBuilder("** ***********************"),
                new StringBuilder("*      *              G  *"),
                new StringBuilder("*  *      *********** *  *"),
                new StringBuilder("*    *        ******* *  *"),
                new StringBuilder("*       *                *"),
                new StringBuilder("**************************"),
            };
            Point start = new Point(1, 1,null);

            //最短経路を探索する
            Queue<Point> queque = new Queue<Point>();
            queque.Enqueue(start);

            while (queque.Count > 0)
            {
                Point now = queque.Dequeue();
                if (maze[now.y][now.x] == BreakChar)
                    Console.WriteLine("break");
                if (maze[now.y][now.x] == WallChar || maze[now.y][now.x] == BeforeChar)
                    continue;
                else if (maze[now.y][now.x] == GoalChar)
                {
                    Point p = now.before;
                    while (p != null)
                    {
                        maze[p.y][p.x] = '@';
                        p = p.before;
                    }
                    break;
                }

                if (maze[now.y - 1][now.x] != '#')
                {
                    queque.Enqueue(new Point(now.x, now.y - 1, now));
                    maze[now.y][now.x] = '.';
                }
                if (maze[now.y][now.x + 1] != '#')
                {
                    queque.Enqueue(new Point(now.x + 1, now.y, now));
                    maze[now.y][now.x] = '.';
                }
                if (maze[now.y + 1][now.x] != '#')
                {
                    queque.Enqueue(new Point(now.x, now.y + 1, now));
                    maze[now.y][now.x] = '.';
                }
                if (maze[now.y][now.x - 1] != '#')
                {
                    queque.Enqueue(new Point(now.x - 1, now.y, now));
                    maze[now.y][now.x] = '.';
                }
            }

            //結果を出力する
            foreach (StringBuilder s in maze)
                Console.WriteLine(s.ToString().Replace(BeforeChar,' '));

            Console.ReadLine();
        }
    }
}
<||

Permalink | 記事への反応(0) | 04:40

ツイートシェア