迷路探索のプログラム

************************************************************
S...**+++**************************++++++++++++++++*********
***..++++++++++++++*******      ***+**************++++******
*** .******************************+*****************+******
****...............................+++++++++***+++++++******
************************ *********.********+*++++***********
************************ *********.********+****+***********
***                        *******.********++++++++++++++***
****** ************************** .......++*********+*******
****** *********************************.***********+*******
****** *****************************  ...***********+*******
**     *******************************.*****+++++++++*******
******       ************ ************.*****+***************
***********  ************* ***********.*****+***************
*********** ************** ********....*****+++++++++*******
********    ************** *****....****************+*******
***********  ****          ***  .********   **+++++++*******
*********** *************  *****.............***************
********                ********************...............G
************************************************************

前田稔(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)