/******************************************/
/*  経路探索（アスキーアート）            */
/*                                        */
/*  領域には壁が設定されている            */
/*  開始位置から目的方向に経路探索をする  */
/*  終了位置に到達したら終了する          */
/******************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define  TMAX 1000                                      // 試行回数MAX
#define  XMAX  60                                       // 領域水平方向MAX
#define  YMAX  30                                       // 領域垂直方向MAX

char  buf[YMAX][XMAX];                                  // 領域配列
int   xS=0,xE=XMAX-1;                                   // 開始位置
int   yS=0,yE=YMAX-1;                                   // 終了位置

void  INIbuf(void);                                     // 領域設定

void  main( )
{
    char  Sc=',';                                       // 探索者の文字
    int   x,y,dx,dy;                                    // 探索者位置
    int   waFG=0;                                       // 壁フラグ
    int   i,j;
    unsigned long seed;                                 // 乱数の種

    printf("\n経路探索（ＡＡ）\n");

    time(&seed);                                        // 時刻取得(秒)
    srand(seed);                                        // 乱数の種をまく

    INIbuf( );                                          // 領域設定
    x=xS; y=yS;                                         // 最初の位置

    for( j=0; j<TMAX; j++ )
      {
        if ( waFG==0 )                                  // 壁なしのとき
          {
            if ( x<xE ) dx= 1; else
            if ( x>xE ) dx=-1; else dx=0;

            if ( y<yE ) dy= 1; else
            if ( y>yE ) dy=-1; else dy=0;
          }
        else                                            // 壁ありのとき
          {
            dx=rand( )%3-1;                             // 移動量x(-1,0,1)
            if ( x==0 && dx<0 ) continue;               // 左端
            if ( x==XMAX-1 && dx>0 ) continue;          // 右端

            dy=rand( )%3-1;                             // 移動量y(-1,0,1)
            if ( y==0 && dy<0 ) continue;               // 上端
            if ( y==YMAX-1 && dy>0 ) continue;          // 下端
          }

        if ( dx==0 && dy==0 ) continue;                 // 移動なし
        if ( buf[y+dy][x+dx]=='X' )                     // 壁あり
          { waFG=1; continue; }

        x+=dx; y+=dy;                                   // 探索者位置更新
        if ( x==xE && y==yE ) break;                    // 終了位置到達

        buf[y][x]=Sc;                                   // 探索者通過
        waFG=0;
      }

    //--結果表示--
    for( y=0; y<YMAX; y++ )
      { printf("\n%.*s",XMAX,&buf[y][0]); }             // １行表示
    printf("\n試行回数=%d",j);
    if ( j>=TMAX ) printf(" 探索失敗！！");
    printf("\n");
}


void  INIbuf( )
/*------------*/
/*  領域設定  */
/*------------*/
{
    memcpy(&buf[ 0][0],"S                      XXXXXXXXXXX                          ",XMAX);
    memcpy(&buf[ 1][0],"XXXX                   XXXXXXXXXXX                          ",XMAX);
    memcpy(&buf[ 2][0],"XXXX    XXXXX                                               ",XMAX);
    memcpy(&buf[ 3][0],"        XXXXXXXXXXXXXX             XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 4][0],"     XXXXXXXXXXXX                  XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 5][0],"     XXXXXXXXXXXX                  XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 6][0],"     XXXXXXXXXXXX                  XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 7][0],"          XXXXXXXXXXXX             XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 8][0],"          XXXXXXXXXXXX             XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 9][0],"          XXXXXXXXXXXX                                      ",XMAX);
    memcpy(&buf[10][0],"          XXXXXXXXXXXX                                      ",XMAX);
    memcpy(&buf[11][0],"                           XXXXXXXXXXXXXXX                  ",XMAX);
    memcpy(&buf[12][0],"     XXX                   XXXXXXXXXXXXXXX     XXXXXXXXX    ",XMAX);
    memcpy(&buf[13][0],"     XXX                   XXXXXXXXXXXXXXX     XXXXXXXXX    ",XMAX);
    memcpy(&buf[14][0],"     XXX   XXXXXXXXXXXXX          XXXXXXXX     XXXXXXXXX    ",XMAX);
    memcpy(&buf[15][0],"           XXXXXXXXXXXXX          XXXXXXXX                  ",XMAX);
    memcpy(&buf[16][0],"           XXXXXXXXXXXXX   XXXXXX     XXXX                  ",XMAX);
    memcpy(&buf[17][0],"   XXXXXXXXXXXXXXXXXX      XXXXXX     XXXX                  ",XMAX);
    memcpy(&buf[18][0],"   XXXXXXXXXXXXXXXXXX      XXXXX  XXXXXXXX                  ",XMAX);
    memcpy(&buf[19][0],"   XXXXXXXXXXXXXXXXXX                                       ",XMAX);
    memcpy(&buf[20][0],"                               XXXXXXX                      ",XMAX);
    memcpy(&buf[21][0],"            XXXXXXX            XXXXXXX                      ",XMAX);
    memcpy(&buf[22][0],"            XXXXXXX   XXXXXXXXXXXXX      XXXXXXXXXXXXXX     ",XMAX);
    memcpy(&buf[23][0],"      XXXXXXXXXXXXX   XXXXXXXXXXXXX      XXXXXXXXXXXXXX     ",XMAX);
    memcpy(&buf[24][0],"      XXXXXXX         XXXXXXXXXXXXX       XXXXXXXXXXX       ",XMAX);
    memcpy(&buf[25][0],"      XXXXXXX             XXXXXXXXX       XXXXXXXXXXX       ",XMAX);
    memcpy(&buf[26][0],"      XXXXXXX             XXXXXXXXX    XXXXXXXXXXXXXX       ",XMAX);
    memcpy(&buf[27][0],"      XXXXXXX         XXXXXXXXXXXXX    XXXXXXXXXXXXXX       ",XMAX);
    memcpy(&buf[28][0],"                      XXXXXXXXXXXXX                         ",XMAX);
    memcpy(&buf[29][0],"                                                            ",XMAX);

    buf[yS][xS]='S'; buf[yE][xE]='G';
}