DouKaku?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define STR_LEN 512 

int deque(struct box *b);
void print_pass();
void pop(struct box **pass_tail);
void push(struct box *b, struct box **pass_tail);
void link_up_down(struct box **head1, struct box **head2, struct box **tail2);
void link_right_left(int type, struct box **head, struct box **tail);
void read_maze(FILE *fp);
int visit(struct box *b, struct box **pass_head, struct box **pass_tail);
int main(void);

struct box{
    int flag;            //-1=壁, 0=通路, 1=通過, 8=スタート, 9=ゴール 
    struct box *up;        //上のマスへのポインタ
    struct box *down;    //下のマスへのポインタ
    struct box *right;    //右のマスへのポインタ
    struct box *left;    //左のマスへのポインタ
    struct box *pass_next;   //探索経路上、次のマスへのポインタ
    struct box *pass_prev;   //探索経路上、前のマスへのポインタ
};

struct box *null = (struct box *)NULL;    //リストの終端として利用
struct box *start, *goal;                //スタート及びゴール

//リストの先頭から方向を示す整数を返す[経路出力用]
int deque(struct box *b){
    if(b->pass_next == b->up) return 0;
    if(b->pass_next == b->down) return 1;
    if(b->pass_next == b->right) return 2;
    if(b->pass_next == b->left) return 3;
    return -1;
}

//戻りなし経路の表示
void print_pass()
{
    static const char *dirstr[] = {"up", "down", "right", "left"};
    struct box *b;
    for(b = start; b != goal; b = b->pass_next) {//スタートからゴールまで
        printf("%s ", dirstr[deque(b)]);//探索した経路を表示していく
    }
}

//リストの最後の要素を削除する[経路出力用]
void pop(struct box **pass_tail) 
{
    struct box *b = *pass_tail;
    *pass_tail = b->pass_prev;//前のマスに戻る
    b->pass_prev->pass_next = null;//リンクの削除
    b->pass_prev = null;
}

//リストの最後に要素を追加する[経路出力用]
void push(struct box *b, struct box **pass_tail){

    b->pass_prev = *pass_tail;//次のマスから前のマスへのリンク
    b->pass_prev->pass_next = b;//前のマスから次のマスへのリンク
    *pass_tail = b;//次のマスに進む
}

//up及びdownのリンクを作成する
void link_up_down(struct box **head1, struct box **head2, struct box **tail2){

    if(*head2 == null) {//リストが空ならば
        *head2 = *head1;//read_mazeで読み込んだ行の左端を迷路の左上端とする
    } else {
        struct box *p1, *p2;//p1は現在の行の分、p2は前の行の分
        for(p1 = *head1, p2 = *tail2; p1 != null && p2 != null; p1 = p1->right, p2 = p2->right) {//1行読み込む
            p1->up = p2;//現在のマスから上へのリンク
            p1->up->down = p1;//上から現在のマスへのリンク
        }
    }
    *tail2 = *head1;//tail2の更新
}

//right及びleftのリンクを作成する。
void link_right_left(int type, struct box **head, struct box **tail) {
    /* この関数内でのリストは，引数で**head,**tailとして与えられているので，*head,*tailで扱う．*/
    // typeで指定されたboxを作成する．
    struct box *p = (struct box*)malloc(sizeof(struct box));

    /* boxであるp の flag , right , leftを決定 */

    p->flag = type;//それぞれ初期化。左右リンク作成前なので、type以外をnullとしておく
    p->up = p->down = p->left = p->right = p->pass_next = p->pass_prev = null;
    if(*head == null) { // もしリストがカラだったら，リストの要素がないのだから p が先頭
        *head = p;//リストの先頭に追加する
    } else {
        p->left = *tail;//前のマスへのリンク
        p->left->right = p;//左から現在のマスへのリンク
    }
    *tail = p;//リストの末尾をpとする
}

//迷路データを読み込む
void read_maze(FILE *fp)
{
    struct box *head1,*tail1,*head2,*tail2;//それぞれ左右のリンクの左端と右端、迷路全体の左上と左下
    unsigned int i;
    char buffer[STR_LEN];//読み込んだ行の保管用

    //１本ずつ左右のリストを生成し、２本のリストから上下のリンクを生成する。
    head2 = tail2 = null;//端二か所を空のリストとする
    while(!feof(fp)){//ファイルの終わりまで

        head1 = tail1 = null;//左右リンクの端を空のリストとする

        if(fgets(buffer, STR_LEN - 1, fp) == NULL) //ファイルから読み込み
            break;
        for(i = 0; i < strlen(buffer) - 1; i++){//読み込んだ行の文字数だけ

            // ファイル中の文字(char型)を整数(int型)で表す
            int type;
            switch(buffer[i]) {
            case '*':
                type = -1;
                break;
            case '0':
            case '8':
            case '9':
                type = buffer[i] - '0';
                break;
            default:
                printf("迷路データに規定外の文字'%c'があります。\n", buffer[i]);
                return ;
            }

            // 左右リンクを作成
            link_right_left(type, &head1, &tail1);

            // startとgoalの決定
            if(type == 8) {
                start = tail1;
            } else if(type == 9) {
                goal = tail1;
            }
        }

        /*  (上下のリンクを生成) */
        link_up_down(&head1,&head2, &tail2);
        
    }
}

int visit(struct box *b, struct box **pass_head, struct box **pass_tail){
    //ゴールならば・・・
    if(b->flag == 9){
        printf("goal!\n");
        return(0);
    }
    
    //現在のマス目を通過済みとする
    if(b->flag == 0) b->flag = 1;
    
    //上方向が空いているなら上にいく
    if(b->up != null && (b->up->flag == 0 || b->up->flag == 9)) {
        printf("up ");
        push(b->up, pass_tail);//経路出力用に、リストの最後に追加しておく
        if(visit(b->up, pass_head, pass_tail) == 0)return(0);//再帰を利用して迷路を探索していく
        pop(pass_tail);//リストの最後を削除する
    }
    
    //下方向が空いているなら下にいく
    if(b->down != null && (b->down->flag == 0 || b->down->flag == 9)) {
        printf("down ");
        push(b->down, pass_tail);
        if(visit(b->down, pass_head, pass_tail) == 0)return(0);
        pop(pass_tail);
    }
    
    //右方向が空いているなら右にいく
    if(b->right != null && (b->right->flag == 0 || b->right->flag == 9)) {
        printf("right ");
        push(b->right, pass_tail);
        if(visit(b->right, pass_head, pass_tail) == 0)return(0);
        pop(pass_tail);
    }

    //左方向が空いているなら左にいく
    if(b->left != null && (b->left->flag == 0 || b->left->flag == 9)) {
        printf("left ");
        push(b->left, pass_tail);
        if(visit(b->left, pass_head, pass_tail) == 0)return(0);
        pop(pass_tail);
    }

    //4方向行き詰まりなので前のマスへ戻る
    printf("return! "); 

    //現在のマス目を未通過に戻す
    b->flag = 0;

    return(1);
}

int main(void){
    FILE *fp;
    int menu=-1;/* メニュー用*/
    char fileName[STR_LEN];    //迷路データファイル名
    struct box *pass_head=null,*pass_tail=null;

    //迷路データファイル名の決定
    while(menu < 0 || menu > 3)
    {
        printf("0.終了\n");
        printf("1. meirodata.txt を読み込む\n");
        printf("2. data.txt を読み込む\n");
        printf("3. 読み込むファイルを指定する\n");
        printf("メニューから選択して下さい。 : ");
        scanf("%d",&menu);
    }

    if(menu==0)return(0);
    if(menu==1)strcpy(fileName,"meirodata.txt");
    if(menu==2)strcpy(fileName,"data.txt");
    if(menu==3)
        scanf("%s",fileName);

    //ファイルを開く
    if((fp = fopen(fileName, "r")) == NULL){
        fprintf(stderr, "file read error!\n");
        exit(1);
    }
    //迷路を読み込む
    read_maze(fp);
    fclose(fp);
    //経路を探索する
    printf("探索経路----------\n");
    pass_head = pass_tail = start;
    visit(start,&pass_head,&pass_tail);
    printf("戻りなし経路----------\n");

    print_pass();

    printf("goal!\n------------------\n");

    return(0);
}