迷路の最短経路を求めるアルゴリズムのソースがうまくいきません。

Question

迷路のアルゴリズムのコード

最終的に出てくる数列が、迷路の最短経路になるはずなのですが、うまくいきませんでした。
自分でも検証してみましたが、間違っているところのご指摘お願いします。
※課題の答え合わせをしているのではないかというご指摘がありましたので説明しますと、
この問題は平成31年度の筑波大学の編入試験の問題で、
答えが公開されていないため、以下のソースコードに誤りがあるところをお聞きできればと質問させていただいた次第です。

発生している問題

3503535353535
35353535353535
35353535353535
35353535353535
35353535353535
と表示されてしまう。
(目的の数列は以下）
3503535353535
3513578935
352356351035
353456735
3535353535835

該当のソースコード

#include<stdio.h>
#define X_size 7
#define Y_size 5
int maze[X_size][Y_size] = {
    {1,1,1,1,1},
    {0,0,0,0,1},{1,1,1,0,1},
    {1,0,0,0,1},{1,0,1,0,1},
    {1,0,0,0,0},{1,1,1,1,1}
};
int ok(int x, int y){
    if (maze[x][y]==0)
    {
        return 1;
    }else{
        return 0;
    }
}
int dist[X_size][Y_size];
void init_dist(void){
    int x,y;
    for(int x=0; x < X_size; x++){
        for(int y =0; y < Y_size; y++){
            dist[x][y]= X_size * Y_size;
        }
    }
}
int update_dist(int x1,int y1,int x2,int y2){
    if(ok(x1,y1) == 1 && ok(x2,y2) == 1){
        if (dist[x2][y2] > dist[x1][y2] + 1){
            dist[x2][y2] = dist[x1][y1] + 1;
            return 1;
        }
    }
    return 0;
}

int main(void) {
    int changed,x,y;
    init_dist();
    dist[1][0]= 0;
    do{
        changed=0;
        for(y=0;y<Y_size;y++){
            for(x=0;x<X_size;x++){
                update_dist(x,y,x-1,y);
                changed += update_dist(x,y,x-1,y);
                update_dist(x,y,x+1,y);
                changed += update_dist(x,y,x+1,y);
                update_dist(x,y,x,y-1);
                changed += update_dist(x,y,x,y-1);
                update_dist(x,y,x,y+1);
                changed += update_dist(x,y,x,y+1);
            }
        }
    }while(changed);
    for(y=0;y<Y_size;y++){
        for(x=0;x<X_size;x++){
            printf("%d",dist[x][y]);
        }
        printf("\n");
    }
    return 0;
}

試したこと

関数の宣言まではうまくいっていることは確認したので、mainのdo文の中がおかしいのかなとおもいます。
update_dist()がおかしいみたいです

補足情報

Comments

[退会済みユーザー]

課題の答え合わせはここでは不適切

[Orlofsky]

宿題は自力でやりましょう。

Answer 1

まぁ、学校の課題を丸投げしているんじゃなくて、「入試の過去問を解いているだけ」だと思うので...
それなりに努力もしてますし。

int update_dist(int x1,int y1,int x2,int y2){
    if(ok(x1,y1) == 1 && ok(x2,y2) == 1){
        if (dist[x2][y2] > dist[x1][y2] + 1){
            dist[x2][y2] = dist[x1][y1] + 1;
            return 1;
        }
    }
    return 0;
}

この関数内のif()の判定ですが、添字に与えるべき変数が間違っていますね。
常にx1, x2とx2, y2の組み合わせになるべきなのに、間違っている場所があります。

しかし、それ以外にも修正すべき点が8ヶ所（修正方法によっては5ヶ所かな？）ありますが、そこはヒントに留めておきたいと思います。

1. update_dist()の呼び出しを余計にしています（4ヶ所）。これだと、同じ箇所を二回判定していることになりませんか？
2. fanaさんもご指摘のように、ok()関数か、もしくはfor()ループ内で、xとyが配列の定義で指定された添字内であるか判定の判定をする必要があります。そのままだと迷路の範囲外まで読みに行ってしまい、想定外の結果になる可能性があります。

がんばってください。

---

でも、入試の問題ってもっとシンプルな答えになりそうな気がするんですけど...
もしかして私は落ちてる？

###追伸
上記1. の「余計な呼び出し」ですが、よく考えたら（考えなくても）答えそのものは変わりませんね。でも、どのように採点されるのかわかりませんから、余計な記述は消した方が良いとは思います。

Comments

[KentaroT]

添字見落としてるとは思いませんでした。
ヒントいただいたところですが、1つめは問題に上下左右を参照するよう指示がありました。(tsukubadepotさんのおっしゃられているのは幅優先探索のことかと思います)
2つめはok()関数の方で解決しました。
ありがとうございます。

[TsukubaDepot]

1. について。
以下の処理

update_dist(x,y,x-1,y); /* (1) */
changed += update_dist(x,y,x-1,y); /* (2) */

ですが、(1)の呼び出しは不要ですよね。結果には影響しませんが、意味のない処理です。
update_dist()関数に関係する他の3つの処理でも、同じように意味のない処理をやっていますね。

[KentaroT]

質問投稿した後にこの部分は直してたのですが、反映するのを忘れてました。お手数おかけしました。ご丁寧なご指摘ありがとうございました。

[TsukubaDepot]

いえいえ。良い体操になりました。

あとは、過去問の引用元は記述しておいた方がいいですね。

Answer 2

面倒そうなので全部見てませんけども，
とりあえずぱっと見で，関数ok()の実装がやばそう．範囲外チェックが無い的な意味で．