2015年03月22日

C#で道順を数える

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

■問題 (出題者:E_Mattsan さん)
図.1のような。格子状の経路があるとします。
(1) このときPからQまでいくのに何通りの経路があるか数えてください。ただし遠回りはせずかならずQに近づく方向に進む(右方向か下方向にだけ進む)とします。

(2) (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。


P-+-+-+    P-+-+-+
| | | |    | | | |
+-+-+-+    +-+-+-+
| | | |    |   | |
+-+-+-+    +-+-+ +
| | | |    | | | |
+-+-+-+    +-+ +-+
| | | |    | | | |
+-+-+-Q    +-+-+-Q
   図.1       図.2

経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。

※問題は、野紾昭弘「離散数学『数え上げ理論』」(講談社 ブルーバックス)「第3章 道順を数える」から拝借させて頂きました。

プログラマらしく、再帰処理で愚直にカウントしています。つまり、(1) も (2) も同じコードで解を求めています。

上記「離散数学『数え上げ理論』」にはどのような解法が載っているのだろうか?
きっと、数学者は、僕には思いもよらない方法を導き出すんだろうな。

なお、左上にPがあることを前提としています。
データは、テキストファイルとして与えています。

using System;
using System.IO;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            string[] lines = File.ReadAllLines("MapData.txt");

            Solver map = new Solver(lines);
            Console.WriteLine(map.CountPath());
        }
    }

    class Solver {
        private int xmax;
        private int ymax;
        private string[] lines;

        public Solver(string[] lines) {
            this.lines = lines;
            ymax = lines.Length;
            xmax = lines[0].Length;
        }

        public char this[int x, int y] {
            get { return lines[y][x]; }
        }

        public bool ExistsRight(int x, int y) {
            return (x + 1 < xmax && this[x + 1, y] != ' ');
        }
        public bool ExistsDown(int x, int y) {
            return (y + 1 < ymax && this[x, y + 1] != ' ');
        }

        public int CountPath(int x = 0, int y = 0) {
            if (this[x,y] == 'Q')
                return 1;
            int sum = 0;
            if (ExistsRight(x, y))
                sum += CountPath(x + 2, y);
            if (ExistsDown(x, y))
                sum += CountPath(x, y + 2);
            return sum;
        }
    }
}

実行結果です。

入力ファイル

P-+-+-+
| | | |
+-+-+-+
|   | |
+-+-+ +
| | | |
+-+ +-+
| | | |
+-+-+-Q

出力
15



 

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

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