深さ優先探索が動作しない。
解決したいこと
C言語を学習し始めた最中なのですがスタックを用いた深さ優先探索がうまく動きません。最後のマップを出力する一歩手前で止まっています。
発生している問題・エラー
under flow
Stack Underflow.
該当するソースコード
#include <stdio.h>
#include <stdlib.h>
#define BUF_SIZE 100
#define SIZE_X 20
#define SIZE_Y 10
int visit[SIZE_X][SIZE_Y];
struct coord {
int x; //x座標
int y; //y座標
int px; //一つ前のx座標
int py; //一つ前のy座標
};
struct stack {
struct coord buf[BUF_SIZE];
int top;
};
/*
* push関数
* 機能: スタックへの値のpush操作
* 引数s: 値を挿入するスタック構造体へのポインタ
* 引数p: 挿入する値（座標）
* 返却値: pushに成功すれば1, （overflow等で）失敗すれば-1。
*/
int push(struct stack *s, struct coord p) {
if(s->top > BUF_SIZE){
printf("overflow\n");
return -1;
}
s->buf[s->top] = p;
s->top++;
return 1;
}
/* pop関数
* 機能: スタックからの値のpop操作
* 引数s: 値を取り出すスタック構造体へのポインタ
* 返却値: popに成功すればpopした値へのポインタ、（underflow等で）失敗すればNULL。
*/
struct coord *pop(struct stack *s) {
if(s->top == 0){
printf("under flow\n");
return NULL;
}else{
int n = s->top;
s->top--;
return &(s->buf[s->top]);
}
}
/* display_stack関数
* 機能: スタックの内部（格納されている値）の表示
* 引数s: 内部を表示するスタック構造体へのポインタ
*/
void display_stack(struct stack *s) {
int i = s->top-1;
while(i >= 0){
printf("%d %d\n",s->buf[i].x,s->buf[i].y);
i--;
}
}
/* read_map関数
* 機能: ファイルからマップを読み込む
* 引数map: 読み込んだマップを格納する配列
*/
void read_map(char map[][SIZE_Y]) {
FILE *fp;
int ch;
int i=0;
int j=0;
fp =fopen("meiro1.txt","r");
while((ch = fgetc(fp)) != EOF){
if(ch == '\n'){
j++;
i = 0;
}else{
map[i][j] = ch;
i++;
}
}
fclose(fp);
}
/* print_map関数
* 機能: マップを画面に表示する。
* 引数map: 表示するマップが格納されている配列
*/
void print_map(char map[][SIZE_Y]) {
for(int j=0;j < SIZE_Y;j++){
for(int i=0;i < SIZE_X;i++){
printf("%c",map[i][j]);
}
printf("\n");
}
}
/* record_path関数
* 機能: 探索経路（探索順路）を記録する。新たなマスを探索する毎に、そのマスを記録するために呼び出すこと。
* 引数rec: 探索経路を記録する配列
* 引数x,y: 現在位置の座標
* 引数px,py: 一つ前の位置の座標
*/
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;
}
/* print_path関数
* 機能: 記録した探索経路を基に、SからGまでの経路を表示する。
* 引数map: 表示するマップの配列。これに経路を示す'.'を書き加える
* 引数rec: 探索経路が記録された配列
* 引数gx,gy: ゴールの座標
*/
void print_path(char map[][SIZE_Y], struct coord rec[][SIZE_Y], int gx, int gy) {
int x, y, tx, ty;
// ゴールの位置から始める
x = gx; y = gy;
// ゴールの前の座標に移動（ゴールに'.'を打たない）
tx = rec[x][y].px;
ty = rec[x][y].py;
x = tx; y = ty;
// スタートまで一手ずつ戻りながらmapに'.'を打つ
while(map[tx][ty] != 'S') {
map[tx][ty] = '.';
tx = rec[x][y].px;
ty = rec[x][y].py;
x = tx; y = ty;
}
print_map(map);
}
/**********************
* メイン関数
**********************/
int main(void) {
/***** 変数の宣言（必要に応じて変数を追加すること）*****/
char map[SIZE_X][SIZE_Y]; // マップを格納する配列
struct coord rec[SIZE_X][SIZE_Y]; // 探索経路を記録する配列
struct coord tmp; // 一時変数として利用可能
struct coord *p; // 一時変数として利用可能
struct stack s; // 探索に利用するスタック
int i,j; // ループ変数
int x,y,px,py; // 座標を格納する一時変数
int gx,gy; // ゴールの位置を格納
/***** 各変数の初期化 *****/
s.top = 0;
tmp.x = -1; tmp.y = -1; tmp.px = -1; tmp.py = -1;
for (i=0; i<SIZE_X; i++) {
for (j=0; j<SIZE_Y; j++) {
visit[i][j] = 0;
rec[i][j] = tmp;
}
}
/***** マップの読み込み *****/
read_map(map);
/***** スタート地点をpush *****/
tmp.x = 1; tmp.y = 1; tmp.px = -1; tmp.py = -1;
if (push(&s, tmp) == -1) {
printf("Stack Overflow.\n");
return 1;
}
/***** 探索処理 *****/
while(1) {
// 処理する座標をpop
p = pop(&s);
if (p == NULL) {
printf("Stack Underflow.\n");
return 1;
}
x = p->x, y = p->y; px = p->px; py = p->py;
if(map[x][y] == 'G'){
printf("Goal found:x=%d,y=%d,\n",x,y);
record_path(rec,x,y,px,py);
gx = x;
gy = y;
break;
}
if(map[x][y] == '#'){
continue;
}
if(visit[x][y] ==1) continue;
visit[x][y];
record_path(rec,x,y,px,py);
tmp.x = x;tmp.y = y-1;tmp.px = x;tmp.py = y;
if(push(&s,tmp) < 0) return 1;
tmp.x = x-1;tmp.y = y;tmp.px = x;tmp.py = y;
if(push(&s,tmp) < 0) return 1;
tmp.x = x;tmp.y = y+1;tmp.px = x;tmp.py = y;
if(push(&s,tmp) < 0) return 1;
tmp.x = x+1;tmp.y = y;tmp.px = x;tmp.py = y;
if(push(&s,tmp) < 0) return 1;
}
/***** 探索経路の表示 *****/
print_path(map,rec,gx,gy);
}
meiro1.txtの中身
####################
#S # #
# ### # ########## #
# # # #
### ### #### #### ##
# # # #
# ####### #### # #
# # # # #####
# # # G#
####################
自分で試したこと
print_pathの手前のwhile文でプログラムが終了していたためmapが出力されなかった。
0 likes
