pushが一回しかされない

Question

int main(void){
    int map[ROW][COL];
    int i, j, si, sj, gi, gj, found = 0; 
    int run = 1;
        readMap(map, ROW);
    si = 1;
    sj = 1;
    gi = 8;
    gj = 10;
    
    push(si);
    push(sj);
    
    while(!isStackEmpty() || found != 1){
        j = pop();
        i = pop();
        if (map[i][j] == map[gi][gj]){
            found = 1;
        }else if (map[i][j] != WALL){
            push(i+1);
            push(j);
            push(i);
            push(j+1);
        }
        run++;
        printStack();　　　　　　　　　　　/*途中経過を知るためにここの時の各変数を結果に表示した*/
        printf("%d,%d,%d\n",i,j,run);
    }
    
    if(found == 1){
        printf("ゴールまでの経路あり\n");
    }else{
        printf("ゴールまでの経路なし\n");
    }
    
    return 0;
}

今迷路の探索のプログラムを書いているのですが、コンパイルして迷路を読み込むとどれも「ゴールまでの経路あり」とでます。これは13行目の終了条件の左側（スタックが空なら真の関数）にひっかかって、１回でループが終わってしまうからだと思います。関数は省略してます。

結果：STACK[]
1,1,1 （i,j,run,runがループ回数）
ゴールまでの経路あり

ここで問題なのがなんでpushされないのかです。i,jは１が入っているからpush(i+1)などしたのに結果のSTACK[]は何も入っていません。
なぜだかわかりますか？

Comments

[cateye]

よく分からないのですが、push(),pop()の本体は何処ですか？
“関数は省略してます。”では分かりません・・・

[German_p0tat0]

すみません説明不足でスタックの値を入れるやつと出すやつです。
あと、解決しました。15行目が違ってました。
ありがとうございました。

[cateye]

自己解決→https://teratail.com/help#resolve-myself

[thkana]

質問のコードでは15行目は
j = pop();
ですが、これが違っていたのですか?

Answer 1

まず、簡単な例で実行できるようにしましょう。
例えば、1x3の迷路を作り、真ん中に壁を置いて絶対に到達できない迷路とか…

さて、printStackはループの回数だけ呼び出されるのに、1回しかループしないのはおかしくありませんか？
迷路の大きさは8x10と思われますので、1歩でゴールということはありません

if(map[i][j] == map[gi][gj]) がゴールに着いたか、を示しているようですが、
mapの中身が壁か通路かを表すとしたら、スタートもゴールも必ず通路ですから必ずtrueでしょう

さらに、移動できるのは右、下の2方向しかありませんが、
Sの字のように、上や左に移動しないとクリアできない迷路に対応してないように見えます。
これを考えると、右、左、右、左というループが発生しますので、
一度通った場所は探索から外すという処理が必要になります。

Comments

[Zuishin]

else if で 4 回 push されているので、1 回しかループしないということはないんじゃないでしょうか。

[Zuishin]

ああ、飲み込めました。一回しかループしないのはなぜかという質問に一回しかループしないのはおかしくないかと尋ねていたわけですね。