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

#define  TMAX 500                                       // 試行回数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   wx,wy,w,dst2;                                 // 終了距離2乗
    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++ )
      {
        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; }

        if ( waFG==0 )                                  // 壁なしのとき
          {
            wx=xE-x; wy=yE-y;
            dst2=wx*wx+wy*wy;                           // 終了距離2乗(現在)
            wx=xE-(x+dx); wy=yE-(y+dy);
            w=wx*wx+wy*wy;                              // 終了距離2乗
            if ( w>=dst2 ) 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],"                       XXXXXXXXXXX                          ",XMAX);
    memcpy(&buf[ 1][0],"                       XXXXXXXXXXX                          ",XMAX);
    memcpy(&buf[ 2][0],"                                                            ",XMAX);
    memcpy(&buf[ 3][0],"     XXXXXXXXXXXXXXXXX             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],"     XXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 8][0],"     XXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 9][0],"     XXXXXXXXXXXXXXXXX                                      ",XMAX);
    memcpy(&buf[10][0],"     XXXXXXXXXXXXXXXXX                                      ",XMAX);
    memcpy(&buf[11][0],"                           XXXXXXXXXXXXXXX                  ",XMAX);
    memcpy(&buf[12][0],"     XXX      XXX          XXXXXXXXXXXXXXX     XXXXXXXXX    ",XMAX);
    memcpy(&buf[13][0],"     XXX      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],"   XXX  XXXXXXXXXXXXX      XXXXXX     XXXX                  ",XMAX);
    memcpy(&buf[18][0],"   XXX  XXXXXXXXXXXXX      XXXXX  XXXXXXXX                  ",XMAX);
    memcpy(&buf[19][0],"        XXXXXXXXXXXXX                                       ",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';
}