迷路探索のプログラム

************************************************************
S...**+++**************************++++++++++++++++*********
***..++++++++++++++*******      ***+**************++++******
*** .******************************+*****************+******
****...............................+++++++++***+++++++******
************************ *********.********+*++++***********
************************ *********.********+****+***********
***                        *******.********++++++++++++++***
****** ************************** .......++*********+*******
****** *********************************.***********+*******
****** *****************************  ...***********+*******
**     *******************************.*****+++++++++*******
******       ************ ************.*****+***************
***********  ************* ***********.*****+***************
*********** ************** ********....*****+++++++++*******
********    ************** *****....****************+*******
***********  ****          ***  .********   **+++++++*******
*********** *************  *****.............***************
********                ********************...............G
************************************************************
*で囲まれた迷路を探索してゴールに到達する「C# 再起関数」のプログラムです。
このプログラムは *で囲まれた中を塗りつぶす の応用です。

前田稔(Maeda Minoru)の超初心者のプログラム入門

プログラムの説明

  1. 次のファイルを格納して下さい。
    /*****************************/
    /*★ 迷路探索     前田 稔 ★*/
    /*****************************/
    using System;
    
    class Prog
    {
        static string[] st =
    //  "....:....1....:....2....:....3....:....4....:....5....:....6",
    {   "************************************************************",  //1
        "S   **   **************************                *********",  //2
        "***                *******      *** **************    ******",  //3
        "***  ****************************** ***************** ******",  //4
        "****                                        ***       ******",  //5
        "************************ ********* ******** *    ***********",
        "************************ ********* ******** **** ***********",
        "***                        ******* ********              ***",
        "****** **************************          ********* *******",
        "****** ********************************* *********** *******",  //10
        "****** *****************************     *********** *******",
        "**     ******************************* *****         *******",
        "******       ************ ************ ***** ***************",
        "***********  ************* *********** ***** ***************",
        "*********** ************** ********    *****         *******",  //15
        "********    ************** *****    **************** *******",
        "***********  ****          ***   ********   **       *******",
        "*********** *************  *****             ***************",
        "********                ********************               G",
        "************************************************************"   //20
    };
    //  "....:....1....:....2....:....3....:....4....:....5....:....6",
        static char[,]  t = new char[20,60];
        //★Main() 関数
        public static void Main()
        {
            int x,y;
    
            //string[] st を char[,] t に格納
            for (y = 0; y < 20; y++)
                for (x = 0; x < 60; x++)    t[y, x] = st[y][x];
            //迷路探索
            Meiro(1,1);
            //結果を表示
            for (y = 0; y < 20; y++)
            {   for (x = 0; x < 60; x++)    Console.Write("{0}",t[y,x]);
                Console.WriteLine("");
            }
            Console.ReadLine();
        }
        // 迷路探索
        static bool Meiro(int x,int y)
        {
            if (t[y,x]=='G')    return true;   //Goal
            if (t[y,x]!=' ')    return false;  //行き止まり
            t[y,x]= '.';
            if (Meiro(x+1,y))   return true;
            if (Meiro(x,y+1))   return true;
            if (Meiro(x-1,y))   return true;
            if (Meiro(x,y-1))   return true;
            t[y,x]= '+';
            return false;
        }
    }
    
  2. ページ先頭の画像のように*で囲まれた迷路を探索してゴールを目指すプログラムを作成します。
    真っ暗な迷路を探索するとき「右手(または左手)を壁にあてて、壁伝いに進むと出口が見つかる」と言うのがあります。
    この考え方をそのままプログラミングしてみました。
    S マークの右から出発して G マークがゴールです。
    このプログラムもループでは手に負えず「再起関数」を使うのですが、塗りつぶしと同じ考え方なので簡単にプログラムできるはずです。 (^_^;
  3. 迷路の定義です。
    ページ先頭の図形を参考に . や + を空白にして定義して下さい。
    連続する空白部分に TAB コードが入らないように注意して下さい。
        static string[] st =
    //  "....:....1....:....2....:....3....:....4....:....5....:....6",
    {   "************************************************************",  //1
        "S   **   **************************                *********",  //2
        "***                *******      *** **************    ******",  //3
                    :
                    :
        "********                ********************               G",
        "************************************************************"   //20
    };
    //  "....:....1....:....2....:....3....:....4....:....5....:....6",
    
  4. 二次元文字列を参照するだけならインデクサが使えるのですが、今回のように置き換えることは出来ません。
    そこで string から二次元 char に格納して、操作することにしました。
    static char[,] t = new char[20,60];
  5. main() 関数では、string[] st を char[,] t に格納します。
    次に、S 座標(1,1)を起点にして Meiro(1,1); 関数を呼び出します。
    最後に迷路をたどった様子を表示します。
  6. 迷路を探索する Meiro() 関数ですが、驚くほど簡単でしょう。
    Meiro() 関数の中から Meiro() 関数を呼び出していることに注目して下さい。
        // 迷路探索
        static bool Meiro(int x,int y)
        {
            if (t[y,x]=='G')    return true;   //Goal
            if (t[y,x]!=' ')    return false;  //行き止まり
            t[y,x]= '.';
            if (Meiro(x+1,y))   return true;
            if (Meiro(x,y+1))   return true;
            if (Meiro(x-1,y))   return true;
            if (Meiro(x,y-1))   return true;
            t[y,x]= '+';
            return false;
        }
        

【演習】

  1. 上下左右をどの順番に呼び出すかで、探索の順序が変わります。
    順番を入れ替えて試してみて下さい。
  2. 行き止まりの迷路に + マークを設定すると、これを避けて進むことにより、二度目からは迷わずにゴールすることができます。

超初心者のプログラム入門(C# Frame Work)