c言語の迷路の最短経路を求めるプログラムでキューのアンダーフローが起きてしまいます。どなたかアドバイスをお願いします。

[arcam]

大学で出た演習問題です。自分でもそれなりに頑張ってみたのですがうまくいきません。以下に問題とソースを記すので、どなたかアドバイスをお願いします。

左上の座標を(0,0) とするマス目でできたNxNマスの迷路があり、
’*’ は壁で、’ ’ は空きマスの通路とする。
このような迷路において、指定したスタートS からゴールG まで、
下記の手順で最短距離を求めるプログラムをつくれ。

手順1: スタート位置の座標=(sx,sy) と距離=0 をキューに記録する
手順2: キューが空になるまで以下を繰り返す。
手順2-1: キューから位置と距離を取り出し、現在の位置と距離とする。
手順2-2: もしその位置がゴールG ならば繰返しを抜ける。
手順2-3: 現在の位置の上下左右を調べ、空きマスならば(現在の距離+1) を
そのマスの距離として座標とともにキューに保存する。
手順3: ゴールに到達していれば距離を出力して終了する。

• N は7 とする。
• 一度通った道を記録するように工夫することで、効率よく計算することもできる。

#include<stdio.h>
#include<stdlib.h>
#define N 7
#define QUEUESIZE 1000000

typedef char elementtype;

struct queue {
int front, rear;
elementtype elements[QUEUESIZE];
};

void initqueue(struct queue *q){
q->front = q->rear = 0;
}
int queueempty(struct queue *q){
return ( q->front==q->rear );
}

void putq(struct queue *q, elementtype x){
q->elements[q->rear]=x;
q->rear++;
if(q->rear>= QUEUESIZE) q->rear=0;
if(q->rear==q->front){
printf("queue overflow"); exit(1);
}
}

elementtype getq(struct queue *q){
elementtype wk;
if(q->front==q->rear){
printf("queue underflow"); exit(1);
}
else {
wk=q->elements[q->front];
q->front++;
if(q->front>=QUEUESIZE) q->front=0;
return wk;
}
}

int main(void) {
#define BUFSIZE (N*2)
char buf[BUFSIZE];
char maze[N][N];
int i, j, sx, sy, gx, gy;
struct queue queue;
initqueue(&queue);
/* 迷路を読み込み、maze にセットする。*/
for (i = 0; i < N; i++) {
fgets(buf, BUFSIZE, stdin);
for (j = 0; j < N && (buf[j] != '\n' && buf[j] != '\0'); j++) {
if (buf[j] == 'S') {
sx = j; sy = i;
} else if (buf[j] == 'G') {
gx = j; gy = i; buf[j] = ' ';
}
maze[j] = buf[j];
}
}
int x=sx,y=sy,c=0;
putq(&queue,x); putq(&queue,y); putq(&queue,c);
while (queue.elements!=NULL) {
x=getq(&queue); y=getq(&queue); c=getq(&queue);　//ここでアンダーフローが起きてしまうようです。
if (x==gx && y==gy) {break;}
if (maze[x+1][y]==' ') {
putq(&queue,x+1); putq(&queue,y); putq(&queue,c+1);
maze[x+1][y]='*';
}
if (maze[x-1][y]==' ') {
putq(&queue,x-1); putq(&queue,y); putq(&queue,c+1);
maze[x-1][y]='*';
}
if (maze[x][y+1]==' ') {
putq(&queue,x); putq(&queue,y+1); putq(&queue,c+1);
maze[x][y+1]='*';
}
if (maze[x][y-1]==' ') {
putq(&queue,x); putq(&queue,y-1); putq(&queue,c+1);
maze[x][y-1]='*';
}
}

/* 最短距離を表示する。*/
printf("%d\n", c);
return 0;
}

[usao]

どんなデータを読み込んでいるのか不明なので，
とりあえず↓のようにmaze[][]に適当なのを入れて動かしてみた感じでは，アンダーフローというのは起きませんでした．

コード:

int main()
{
    char maze[N][N+1] = 
    {//  0123456(y)
        "*******",  //0
        "* *** *",  //1
        "*     *",  //2
        "*  ** *",  //3
        "* * * *",  //4
        "*     *",  //5
        "*******"   //6(x)
    };
    const int sx = 3;
    const int sy = 1;
    const int gx = 4;
    const int gy = 3;
    
    struct queue queue;
    initqueue(&queue);

    int x=sx,y=sy,c=0;
    putq(&queue,x); putq(&queue,y); putq(&queue,c);
    while (queue.elements!=NULL) {
        x=getq(&queue); y=getq(&queue); c=getq(&queue);//ここでアンダーフローが起きてしまうようです。
        if (x==gx && y==gy) {break;}
        if (maze[x+1][y]==' ') {
            putq(&queue,x+1); putq(&queue,y); putq(&queue,c+1);
            maze[x+1][y]='*';
        }
        if (maze[x-1][y]==' ') {
            putq(&queue,x-1); putq(&queue,y); putq(&queue,c+1);
            maze[x-1][y]='*';
        }
        if (maze[x][y+1]==' ') {
            putq(&queue,x); putq(&queue,y+1); putq(&queue,c+1);
            maze[x][y+1]='*';
        }
        if (maze[x][y-1]==' ') {
            putq(&queue,x); putq(&queue,y-1); putq(&queue,c+1);
            maze[x][y-1]='*';
        }
    }

    /* 最短距離を表示する。*/
    printf("%d\n", c);

    return 0;
}

whileの条件が間違っているので，データに不備があるときにアンダーフローするのではないでしょうか．
せっかくqueueが空かどうかを判定する関数を用意されているのですから，使ってはいかがでしょう．

また，このコードだと，データが特定の条件を満たしていないと領域外参照を起こしますね．
・４方向を調べる際に，調べる位置がmaze[][]の領域内かどうかのチェックを入れるべきです
・探索開始する前に，(sx,sy)がまともな位置にあるかどうかもチェック
　関連して，(gx,gy)もまともかどうか確かめてからwhileの探索処理に入る方が良いかと．

とりあえずデータ入力を終えた段階で，データ｛maze[],sx,sy,gx,gy｝
の内容を表示する等して，ちゃんとしたデータになっているかどうかを確かめてみてはいかがでしょうか．

あと，QUEUESIZEが不必要にでかいです．NxNくらいあれば十分では？

[arkam]

アドバイスに従って色々と変えてみました。迷路とその始点と終点の座標はしっかりと読み込まれているのにもかかわらず、相変わらずアンダーフローが起きてしまいます。正しいwhile文を教えてくれるとありがたいです。

#include<stdio.h>
#include<stdlib.h>
#define N 7
#define QUEUESIZE 100

typedef char elementtype;

struct queue {
int front, rear;
elementtype elements[QUEUESIZE];
};

void initqueue(struct queue *q){
q->front = q->rear = 0;
}
int queueempty(struct queue *q){
return ( q->front==q->rear );
}

void putq(struct queue *q, elementtype x){
q->elements[q->rear]=x;
q->rear++;
if(q->rear>= QUEUESIZE) q->rear=0;
if(q->rear==q->front){
printf("queue overflow"); exit(1);
}
}

elementtype getq(struct queue *q){
elementtype wk;
if(q->front==q->rear){
printf("queue underflow"); exit(1);
}
else {
wk=q->elements[q->front];
q->front++;
if(q->front>=QUEUESIZE) q->front=0;
return wk;
}
}

int main(void) {
#define BUFSIZE (N*2)
char buf[BUFSIZE];
char maze[N][N];
int i, j, sx, sy, gx, gy;
struct queue queue;
initqueue(&queue);
/* 迷路を読み込み、maze にセットする。*/
for (i = 0; i < N; i++) {
fgets(buf, BUFSIZE, stdin);
for (j = 0; j < N && (buf[j] != '\n' && buf[j] != '\0'); j++) {
if (buf[j] == 'S') {
sx = j; sy = i;
} else if (buf[j] == 'G') {
gx = j; gy = i; buf[j] = ' ';
}
maze[j] = buf[j];
}
}
for (i=0;i<N;i++) {
for (j=0;j<N;j++) {printf("%c",maze[j]);}
printf("\n");
}
if (0<=sx<N && 0<=sy<N && 0<=gx<N && 0<=gy<N) {
printf("%d,%d,%d,%d\n",sx,sy,gx,gy);
int x=sx,y=sy,c=0;
putq(&queue,x); putq(&queue,y); putq(&queue,c);
while (!queueempty(&queue)) {
x=getq(&queue); y=getq(&queue); c=getq(&queue);
if (x==gx && y==gy) {break;}
if (0<=x+1<N && 0<=x-1<N && 0<=y+1<N && 0<=y-1<N) {
if (maze[x+1][y]==' ') {
putq(&queue,x+1); putq(&queue,y); putq(&queue,c+1);
maze[x+1][y]='*';
}
if (maze[x-1][y]==' ') {
putq(&queue,x-1); putq(&queue,y); putq(&queue,c+1);
maze[x-1][y]='*';
}
if (maze[x][y+1]==' ') {
putq(&queue,x); putq(&queue,y+1); putq(&queue,c+1);
maze[x][y+1]='*';
}
if (maze[x][y-1]==' ') {
putq(&queue,x); putq(&queue,y-1); putq(&queue,c+1);
maze[x][y-1]='*';
}
}
}

printf("%d\n",c);
return 0;
}
}

[usao]

コードが見難いので，フォーラムルールに記載されている方法で投稿してください．

私がコードに直書きしたデータと同じデータ内容になるように入力を行ってもダメでしょうか？
あるいは，あなたが入力している内容を，私が書いたようにコード内にダイレクトに記述してみても
問題が発生するでしょうか？


今回のコードでは，
0<=sx<N
のような記述は　意図した判定結果にはなっていないと思います．
0<=sx && sx<N
のように書かないとダメです．
また，この書き方の件を度外視しても
if (0<=x+1<N && 0<=x-1<N && 0<=y+1<N && 0<=y-1<N)
というのは，判定方法として妥当でしょうか？
例えば，xが0のとき，
maze[x-1][y]は領域外なので避けねばなりませんが
maze[x+1][y]は領域内なので処理せねばなりません．


>アンダーフローが起きてしまいます。
問題が起こるときに，各種データがどうなっているのかを根気よく調査して原因を特定してください．
処理がどのように進んで行ったのかを把握するのに十分な出力を行い，どこで変なことになっているかを見てください．
「想定通りに正しく処理が進んだら，各データが時々刻々とどのように変化していくのか」が把握しやすくて（迷路が狭いとか単純とか）
且つ，問題が発生するような入力データ　を用いると良いでしょう．

[arkham]

迷路の座標の入力をミスしていました。プログラミング以前の問題でした。今はもう無事に作動しています。無駄にご迷惑をかけてしまってすいません。

[usao]

外部からデータ入力がある場合には，そのデータが間違った形（値）である可能性を想定して
そういう場合にもちゃんと対処するようにしておくべきです．
「正しいフォーマット(?)の値を入れたとき　であれば　動きます」では完成とは言い難いと思います．

[解決]ということになっていますが，
少なくとも私がここで指摘したような判定の不備くらいは修正しておいたほうが良いと思いますよ．