/* ■概要
 * 与えた迷路に対する最短ルートを総当りで探索するプログラム。
 * ■留意点
 * 総当りをする際は、ルート順にマップの配列添字を並べた際、より小さいものから調べる。
 * 調べているルートの方が、既に得られた最短距離より長くなる場合は、それ以降のルートはすべて最短ではないので次のルートを探索する。*/

  /* 初期化 */
char *init(int *col, int *row)
{
    *col = 26;
    *row = 13;
    return
    "**************************"
    "*S* *                    *"
    "* * *  *  *************  *"
    "* *   *    ************  *"
    "*    *                   *"
    "************** ***********"
    "*                        *"
    "** ***********************"
    "*      *              G  *"
    "*  *      *********** *  *"
    "*    *        ******* *  *"
    "*       *                *"
    "**************************";
}
 /* スタート地点の取得 */
int getStart(char *map)
{
    int i=0;
    while(map[i++]!='S');
    return i;
}
 /* 示された位置をすでに通過していないか */
int routeCheckPassed(int *route, int pos, int root)
{
    int i=root;
    while(i-->0) if(route[i]==pos) return 0;
    return 1;
}
 /* 示された位置が次の地点としての条件に合うか判定 */
int routeNext_check(char test, char *map, int pos, int min, int max, int *route, int root)
{
    if(pos>min && pos<=max)
    {
        return (map[pos-1]==test && routeCheckPassed(route, pos, root));
    }
    return 0;
}
 /* 次の地点を添え字の小さい順に得る */
int routeNext(char test, char *map, int *route, int root, int min, int col, int row, int size)
{
    int up    = route[root] - col;
    int left  = route[root] - 1;
    int right = route[root] + 1;
    int down  = route[root] + col;
    if(routeNext_check(test,map,up   ,min,size,route,root)) return up;
    if(routeNext_check(test,map,left ,min,size,route,root)) return left;
    if(routeNext_check(test,map,right,min,size,route,root)) return right;
    if(routeNext_check(test,map,down ,min,size,route,root)) return down;
    return 0;
}
 /* ルートを記したマップを表示 */
void routePrint(char *map, int *route, int col, int row, int size)
{
    int r, r2; /* ルート判定用 */
    int i, j;
    char c;
    /* ルートの最小値取得 */
    r = route[i=1];
    while(route[++i]) if(route[i]<r) r=route[i];
    /* 表示 */
    for(i=0;i<size;i++)
    {
        c = map[i];
        if(i%col == 0) putchar('\n'); /* 改行 */
        if(i == r-1)
        {    /* 経路上 */
            c = '$';
            /* 次のルート取得 */
            j = 0; r2 = r; r = size + 1;
            while(route[++j]) if(r>route[j] && route[j]>r2) r=route[j];
        }
        putchar(c);
    }
}
int main(void)
{
    int col, row, size; /* col:列数; row:行数; size:セル数; */
    char *map;      /* 迷路のマップ */
    int *route;     /* 調査中のルート */
    int *shortest;  /* 最短ルート */
    int root;       /* ルート調査の基点 */
    int length;     /* 最短距離 */
    int prev ;      /* 以前のマップ配列添字(ルートを1つ前へ戻った際に記録,存在しない場合は0) */
    int next;       /* 1つ先のルート候補となるマップ配列添字 */
    /* ※ルートに用いるマップ配列添字は1 originとしてマップ処理時に-1する。(0をfalse扱いにしたかったので) */
    
    /* 初期化 */
    map = init(&col, &row);
    size = col * row;
    route = (int*)calloc(size,sizeof(int));
    shortest = (int*)calloc(size,sizeof(int));
    
    /* 探索 */
    root = 0;
    route[0] = getStart(map);
    prev = 0;
    length = size;
    while(root>=0)
    {
        if(root<length-1 && (next = routeNext(' ', map, route, root, prev, col, row, size)))
        {    /* 1つ先へ進む */
            route[++root] = next;
            prev = 0;
            if(routeNext('G', map, route, root, prev, col, row, size))
            {    /* ゴール */
                length = root;
                memcpy(shortest,route,sizeof(int)*size);
                prev = route[root];
                route[root--] = 0;
            }
        }
        else
        {    /* 1つ前へ戻る */
            prev = route[root];
            route[root--] = 0;
        }
    }
    /* 表示 */
    routePrint(map,shortest,col,row,size);
    printf("\nShortest-Length:%d\n",length);
    
    /* 終了 */
    free(route);
    free(shortest);
    return 0;
}

**************************
*S* *$$$$$               *
*$* *$ * $*************  *
*$*$$$*  $$************  *
*$$$ *    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************
Shortest-Length:59