Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

(C言語)スタックを用いた迷路の経路探索のエラーについて

解決したいこと

C言語初心者の学生です。
C言語でスタックを用いて迷路の経路を縦型探索するスクリプトを書いています。VisualStudio2019で以下のスクリプトをデバッグしたところ、「読み取りアクセス違反が発生しました」と表示されるのですが、なぜエラーが発生するのか分からないです。
ブラッシュアップしていきたいので、エラーの原因の推測やスクリプトの書き方の不備など、問題点の指摘や改善方法をご教授願います。

発生している問題・エラー

問題・エラーが起きている画像をここにドラッグアンドドロップ
スクリーンショット (351).png

該当するソースコード

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable : 4996)

#define BUF_SIZE 100
#define SIZE_X 10
#define SIZE_Y 21

struct coord {
    int x;
    int y;
    int px;
    int py;
};

struct stack {
    struct coord buf[BUF_SIZE];
    int top;
};

int push(struct stack* s, struct coord p) {
    if (s->top > BUF_SIZE - 1) {
        return -1;
    }
    s->buf[s->top] = p;
    s->top++;
    return 1;
}

struct coord* pop(struct stack* s) {
    if (s->top <= 0) {
        return NULL;
    }
    struct coord *alt = &s->buf[s->top];
    s->top = s->top - 1;
    return alt;
}

void display_stack(struct stack* s) {
    for (int i = 0; i < s->top; i++) {
        printf("(%d,%d) ", s->buf[i].x, s->buf[i].y);
    }
    printf("\n");
}

void read_map(char map[][SIZE_Y]) {
    FILE* fp;
    if ((fp = fopen("meiro1.txt", "r")) == NULL) {
        printf("File cannot be opened!");
        exit(1);
    }
    for (int i = 0; i < SIZE_X; i++) {
        for (int j = 0; j < SIZE_Y; j++) {
            int ch = fgetc(fp);
            map[i][j] = ch;
        }
    }
    fclose(fp);
}

void print_map(char map[][SIZE_Y]) {
    for (int i = 0; i < SIZE_X; i++) {
        for (int j = 0; j < SIZE_Y; j++) {
            printf("%c", map[i][j]);
        }
    }
}

void record_path(struct coord rec[][SIZE_Y], int x, int y, int px, int py) {
    rec[x][y].px = px;
    rec[x][y].py = py;
}

void print_path(char map[][SIZE_Y], struct coord rec[][SIZE_Y], int gx, int gy) {
    int x = gx;
    int y = gy;
    while (x != -1 && y != -1) {
        map[x][y] = '.';
        int px = rec[x][y].px;
        int py = rec[x][y].py;
        x = px;
        y = py;
    }
    print_map(map);
}

void search(char map[][SIZE_Y], struct coord rec[][SIZE_Y], int visit[][SIZE_Y], struct stack* s, int gx, int gy)
{
    struct coord tmp;
    tmp.x = 1;
    tmp.y = 1;
    tmp.px = -1;
    tmp.py = -1;

    if (push(s, tmp) == -1) {
        printf("Stack Overflow.\n");
        printf("a");
    }

    while (1) {
        struct coord* p = pop(s);
        if (p == NULL) {
            printf("Stack Underflow.\n");
            break;
        }
        int x = p->x;
        int y = p->y;
        int px = p->px;
        int py = p->py;

        // ゴールに到達したら終了
        if (map[x][y] == 'G') {
            record_path(rec, x, y, px, py);
            gx = x;
            gy = y;
            break;
        }

        // 上、下、左、右に進む(縦型探索)
        int dx[] = { -1, 1, 0, 0 };
        int dy[] = { 0, 0, -1, 1 };
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; // 移動先のX座標
            int ny = y + dy[i]; // 移動先のY座標
            if (!(nx < 0 || nx >= SIZE_X || ny < 0 || ny >= SIZE_Y ||
                map[nx][ny] == '#')) { // 迷路の範囲内を探索しているならば
                tmp.x = nx;
                tmp.y = ny;
                tmp.px = x;
                tmp.py = y;
                if (visit[nx][ny] == 1) break;
                else if (push(s, tmp) == -1) {
                    printf("Stack Overflow.\n");
                    printf("i");
                }
                visit[nx][ny] = 1; // 新たに訪れた位置をマーク
            }
        }
    }
}

int main(void) {
    char map[SIZE_X][SIZE_Y];
    struct coord rec[SIZE_X][SIZE_Y];
    int visit[SIZE_X][SIZE_Y] = { 0 }; // 訪問済み配列を0で初期化
    struct stack s;
    int gx=8;
    int gy=18;

    s.top = 0;
    for (int i = 0; i < SIZE_X; i++) {
        for (int j = 0; j < SIZE_Y; j++) {
            rec[i][j].x = -1;
            rec[i][j].y = -1;
            rec[i][j].px = -1;
            rec[i][j].py = -1;
            if (map[i][j] == 'G') {
                gx = i;
                gy = j;
            }
        }
    }

    read_map(map);
    print_map(map);

    search(map, rec, visit, &s, gx, gy);
    print_path(map, rec, gx, gy);

    return 0;
}

自分で試したこと

エラーの原因が分からないため、何もできていないです。
他のエラーや警告は表示されていないです。

0

2Answer

line#112 if (map[x][y] == 'G')で、配列外参照を起こしていると思われます。
"meiro1.txt"の内容を提示してもらえますか?

0Like

Comments

  1. おそらく、pop関数でのスタックのインデックスの使い方が悪いと思います。

    struct coord* pop(struct stack* s) {
        if (s->top <= 0) {
            return NULL;
        }
    -   struct coord *alt = &s->buf[s->top];
        s->top = s->top - 1;
    +   struct coord *alt = &s->buf[s->top];
        return alt;
    }
    

    s->topは次のpushで格納する位置(つまりnext)を指しているので、popする時は、インデックスを先に戻してから参照するのが正しいと思います。

こちらが中身です。迷路は10×20です(改行文字含めず)。スペース含め文字は全て半角文字で、各行は最後に改行してます。IMG_9712.jpeg

0Like

Comments

  1. 入れ違いになりましたが、先のコメントを見てください。(pop関数)

    次に、search関数の最後の2つの引数gxgyは何を表しているのでしょうか?
    mainから呼ぶときはゴールの座標を渡しているように見えますが、searchではその値を上書きしていますが、意味が無い処理です。

  2. だいぶ直しましたが、おそらく期待通りに動いていると思います。

    ####################
    #S    #            #
    # ### # ########## #
    #     #      #     #
    ### ### #### #### ##
    #     #      #     #
    # ####### #### #   #
    #  #   #  #    #####
    #    #    #       G#
    ####################
    
    ####################
    #.....#............#
    # ###.#.##########.#
    #  ...#......#   ..#
    ###.### ####.####.##
    #...  #  ....#.....#
    #.#######.####.#...#
    #..#...# .#....#####
    # ...#....#........#
    ####################
    
    #include <stdio.h>
    #include <stdlib.h>
    #pragma warning(disable : 4996)
    
    #define BUF_SIZE 100
    #define SIZE_X 10
    #define SIZE_Y 21
    
    struct coord {
        int x;
        int y;
        int px;
        int py;
    };
    
    struct stack {
        struct coord buf[BUF_SIZE];
        int top;
    };
    
    int push(struct stack* s, struct coord p) {
        if (s->top > BUF_SIZE - 1) {
            return -1;
        }
        s->buf[s->top] = p;
        s->top++;
        return 1;
    }
    
    struct coord* pop(struct stack* s) {
        if (s->top <= 0) {
            return NULL;
        }
        s->top = s->top - 1;
        struct coord *alt = &s->buf[s->top];
        return alt;
    }
    
    void display_stack(struct stack* s) {
        for (int i = 0; i < s->top; i++) {
            printf("(%d,%d) ", s->buf[i].x, s->buf[i].y);
        }
        printf("\n");
    }
    
    void read_map(char map[][SIZE_Y]) {
        FILE* fp;
        if ((fp = fopen("meiro1.txt", "r")) == NULL) {
            printf("File cannot be opened!");
            exit(1);
        }
        for (int i = 0; i < SIZE_X; i++) {
            for (int j = 0; j < SIZE_Y; j++) {
                int ch = fgetc(fp);
                map[i][j] = ch;
            }
        }
        fclose(fp);
    }
    
    void print_map(char map[][SIZE_Y]) {
        for (int i = 0; i < SIZE_X; i++) {
            for (int j = 0; j < SIZE_Y; j++) {
                printf("%c", map[i][j]);
            }
        }
    }
    
    void record_path(struct coord rec[][SIZE_Y], int x, int y, int px, int py) {
        rec[x][y].px = px;
        rec[x][y].py = py;
    }
    
    void print_path(char map[][SIZE_Y], struct coord rec[][SIZE_Y], int gx, int gy) {
        int x = gx;
        int y = gy;
        while (x != -1 && y != -1) {
            map[x][y] = '.';
            int px = rec[x][y].px;
            int py = rec[x][y].py;
            x = px;
            y = py;
        }
        print_map(map);
    }
    
    void search(char map[][SIZE_Y], struct coord rec[][SIZE_Y], int visit[][SIZE_Y], struct stack* s, int* gx, int* gy)
    {
        struct coord tmp;
        tmp.x = *gx;
        tmp.y = *gy;
        tmp.px = -1;
        tmp.py = -1;
        
        if (push(s, tmp) == -1) {
            printf("Stack Overflow.\n");
            printf("a");
        }
        
        while (1) {
            struct coord* p = pop(s);
            if (p == NULL) {
                printf("Stack Underflow.\n");
                break;
            }
            int x = p->x;
            int y = p->y;
            int px = p->px;
            int py = p->py;
            
            visit[x][y] = 1; // 新たに訪れた位置をマーク
            record_path(rec, x, y, px, py);
    
            // ゴールに到達したら終了
            if (map[x][y] == 'G') {
                *gx = x;
                *gy = y;
                break;
            }
            
            // 上、下、左、右に進む(縦型探索)
            int dx[] = { -1, 1, 0, 0 };
            int dy[] = { 0, 0, -1, 1 };
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i]; // 移動先のX座標
                int ny = y + dy[i]; // 移動先のY座標
                if (!(nx < 0 || nx >= SIZE_X || ny < 0 || ny >= SIZE_Y ||
                      map[nx][ny] == '#')) { // 迷路の範囲内を探索しているならば
                    tmp.x = nx;
                    tmp.y = ny;
                    tmp.px = x;
                    tmp.py = y;
                    if (visit[nx][ny] == 1) continue;
                    else if (push(s, tmp) == -1) {
                        printf("Stack Overflow.\n");
                        printf("i");
                    }
                }
            }
        }
    }
    
    int main(int argc, const char * argv[]) {
        char map[SIZE_X][SIZE_Y];
        struct coord rec[SIZE_X][SIZE_Y];
        int visit[SIZE_X][SIZE_Y] = { 0 }; // 訪問済み配列を0で初期化
        struct stack s;
        int gx=0;
        int gy=0;
    
        read_map(map);
    
        s.top = 0;
        for (int i = 0; i < SIZE_X; i++) {
            for (int j = 0; j < SIZE_Y; j++) {
                rec[i][j].x = -1;
                rec[i][j].y = -1;
                rec[i][j].px = -1;
                rec[i][j].py = -1;
                if (map[i][j] == 'S') {
                    gx = i;
                    gy = j;
                }
            }
        }
    
        print_map(map);
        
        search(map, rec, visit, &s, &gx, &gy);
        print_path(map, rec, gx, gy);
        
        return 0;
    }
    

    変更箇所は元のコードとコンペア(diff)して確認してください。変更内容に不明点があれば引き続きQ&Aしてください。


    diffのスクショを貼っておきます。

    IMG_2043.JPEG

  3. 一点、補足しておきます。
    最初のソースコードだと、スタート座標(1,1)とゴール座標(8,18)がハードコードされていました。せっかく迷路データをファイルから入力しているので、スタート座標を入力した迷路データから取得するようにしています。
    そのため、メインのgx,gy変数に初めはスタート座標を設定してsearch関数に渡すようにしたのと、search関数でゴールしたときに、今度はゴール座標をgx,gy変数に上書きしてメインに戻すようにしています。そのため、gx,gy変数のポインタをsearch関数に渡すように変更しています。

  4. @TmgHrkk

    Questioner

    ありがとうございます。パソコンの電池が切れてしまったのでこんな時間の返信になってしまいました。すいません。こちらでも上手く動作しました。再代入が可読性を下げてしまっていますね。ご指摘ありがとうございます。

Your answer might help someone💌