/******************************************/
/* 経路探索（アスキーアート） */
/* */
/* 領域には壁が設定されている */
/* 開始位置からランダムに経路探索をする */
/* 終了位置に到達したら終了する */
/******************************************/
#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';
}
|
