迷路探索のプログラム

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

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

プログラムの説明

  1. ソースプログラムです。
    ファイル名 説明
    Meiro.cpp 迷路探索
  2. ページ先頭の画像のように*で囲まれた迷路を探索してゴールを目指すプログラムを作成します。
    S マークの右から出発して G マークがゴールです。
    このプログラムもループでは手に負えず「再起関数」を使うのですが、塗りつぶしと同じ考え方なので簡単に プログラムできるはずです。 (^_^;
  3. 迷路の定義です。
    ページ先頭の図形を参考に . や + を空白にして定義して下さい。
    連続する空白部分に TAB コードが入らないように注意して下さい。
        /*★ 迷路探索     前田  稔 ★*/
        #include <stdio.h>
        char    t[20][60]=
        //  "....:....1....:....2....:....3....:....4....:....5....:....6",
        {   "***********************************************************",  //1
            "S   **   **************************                ********",  //2
                      ページ先頭の図形を参照して下さい
            "********                ********************              G",
            "***********************************************************"   //20
        };
        
  4. main() 関数では、S マークの右側座標をパラメータとして Meiro() 関数を呼ぶだけです。
    Meiro() では探索した迷路を「.」でマークします。
        //★ MAIN PROGRAM
        int  main()
        {   int     y;
    
            Meiro(1,1);
            for(y=0; y<20; y++)     puts(t[y]);
            return(0);
        }
        
  5. 迷路を探索する int 型の関数です。
    Goal に到達すると 1 をリターンします。
    迷路に行き止まると 0 をリターンします。
    探索した迷路には . を格納します。
    前回の「塗りつぶし」と違い !=' ' で行き止まりを判定します。
        // 迷路探索
        int  Meiro(int x,int y)
        {
            if (t[y][x]=='G')   return 1;   //Goal
            if (t[y][x]!=' ')   return 0;   //行き止まり
                        :
            このあとは各自で考えて下さい。
        }
        

【演習】

  1. Meiro() 関数を完成させてプログラムを実行して下さい。
  2. 上下左右をどの順番でコールするかで、探索の順序が変わります。
    順番を入れ替えて試してみて下さい。
  3. ページ先頭の画像のように行き止まりの迷路に + マークを設定して下さい。
    + マークが設定されると、これを避けて進むことにより、迷わずにゴールすることができます。

超初心者のプログラム入門(C/C++)