2015年04月08日

C#でマップの通り抜け

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その83

■問題 (出題者:にしお さん)
ここにピリオド(.)とプラス(+)と改行で構成された入力ファイルがあります。
ピリオドは通れないマス、プラスは通れるマスを表現しています。 上から下へたどり着く道があるかどうかを判定するコードを書いてください。
通り抜けられる例
.+.....
.+.+++.
.+.+.+.
.+++.+.
.....+.

通り抜けられない例

..+...+
++.+++.
.+...++
++++.+.
.+..+.+


このところ、探索系のプログラムが続きいています。 今回は、深さ優先探索で求めています。
Debugモードでビルドした場合は、その探索過程がわかるようにしています。
そういえば、このシリーズで、Conditional属性を使ったのは始めてかも。

今回作成したプログラムでは、Mapクラスをまず理解すれば、たどり着く道があるかどうかを判定する PassThroughMapクラスを理解するのは、それほど難しくないと思います。
再帰処理と深さ優先探索が分かっているという前提ですが...

すでに通った箇所は、+ を * に変えることで、逆戻りしないようにしています。
最初作成したときは、再帰呼び出しの度に、Mapオブジェクトのクローンを作成し、それを引数として渡していたのですが、それだと、メモリ効率が悪いので、クローンを作成せずに、元の状態に戻れるよう、TurnBackを定義し、メソッドから戻るときにこれを呼び出すようにしています。

経路は、Stackに保存しています。そのほうが、経路を追加したり、取り除いたりする操作が簡単です。 ただし、Stackなので、経路を取り出す際は、反転させています。


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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            string[] map = File.ReadAllLines("Map.txt");
            PassThroughMap p = new PassThroughMap();
            var answer = p.Solve(map);
            Console.WriteLine(answer.Count > 0);
            // 経路を表示する
            foreach (var pt in answer)
                Console.WriteLine(pt);
        }
    }

    public class PassThroughMap {
        private Map map;
        public List<Point> Solve(string[] arg) {
            map = new Map(arg);
            // 開始地点を求め、求まったら SolveInnnerメソッドを呼び出し、解があるかを求める。
            for (int x = 0; x < map.Width; x++) {
                Point p = new Point(x, 0);
                if (map.CanPass(p)) {
                    if (SolveInnner(p) == true)
                        break;
                }
            }
            return map.Route.Reverse().ToList();
        }

        private bool SolveInnner(Point now) {
            if (map.LeavesFootprint(now))
                return true;

            foreach (var p in map.Candidates()) {
                if (SolveInnner(p))
                    return true;
            }
            map.TurnBack(now);
            return false;
        }
    }

    public class Map {
        private char[][] lines;
        private Point _current = new Point(-1,-1);
        public Stack<Point> Route { get; set; }

        public int Width { get; private set; }
        public int Height { get; private set; }

        public Map(string[] lines) {
            Width = lines[0].Length;
            Height = lines.Length;
            this.lines = new char[Height][];
            int y = 0;
            foreach (var line in lines)
                this.lines[y++] = line.ToCharArray();
            Route = new Stack<Point>();
        }

        public bool LeavesFootprint(Point pt) {
            lines[pt.Y][pt.X] = '*';
            _current = pt;
            Route.Push(pt);
            Print();
            return (_current.Y == Height - 1); // 出口か?
        }

        public void TurnBack(Point pt) {
            lines[pt.Y][pt.X] = '+';
            Route.Pop();
            if (Route.Count > 0)
                _current = Route.Peek();
            else
                _current = new Point(-1, -1);
            Print();
        }

        public bool CanPass(Point px) {
            return CanPass(px.X, px.Y);
        }

        private bool CanPass(int x, int y) {
            return (this.lines[y][x] == '+');
        }

        public IEnumerable<Point> Candidates() {
            if (_current.Y + 1 < Height && CanPass(_current.X, _current.Y + 1))
                yield return new Point(_current.X, _current.Y + 1);
            if (_current.X + 1 < Width && CanPass(_current.X + 1, _current.Y))
                yield return new Point(_current.X + 1, _current.Y);
            if (_current.X - 1 >= 0 && CanPass(_current.X - 1, _current.Y))
                yield return new Point(_current.X - 1, _current.Y);
            if (_current.Y - 1 >= 0 && CanPass(_current.X, _current.Y - 1))
                yield return new Point(_current.X, _current.Y - 1);
        }

        [Conditional("DEBUG")]
        public void Print() {
            for (int y = 0; y < Height; y++) {
                for (int x = 0; x < Width; x++) {
                    Console.Write(lines[y][x]);
                }
                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }

    public class Point {
        public int X { get; set; }
        public int Y { get; set; }
        public Point(int x, int y) {
            X = x;
            Y = y;
        }
        public override string ToString() {
            return String.Format("({0},{1})", X, Y);
        }
    }
}

以下、実行結果です。

入力ファイル

.+..+.....
.+.+++++..
.+.+...+..
.+.+.++++.
..+...+.+.
..+..++.+.
....++....
....+.....

出力 (Releaseモード)
True
(4,0)
(4,1)
(5,1)
(6,1)
(7,1)
(7,2)
(7,3)
(6,3)
(6,4)
(6,5)
(5,5)
(5,6)
(4,6)
(4,7)
Debugモードで実行したときは、探索途中のMapの状態が見られるので、 どのように経路を求めているのかが理解しやすいと思います。


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52411747