迷路探索のプログラムでのSegmentation fault

Question

実現したいこと

• 大きいサイズの迷路でもSegmentation faultが出ずに探索できるようにする。

前提

C言語でスタックを用いて迷路探索のプログラムを書こうとしています。
サイズの小さい迷路では問題なく動作することが確認できています。
また分岐に対応していない(１本道の迷路のみに使える)プログラムでは問題なく動作しています。
最初に迷路のサイズの上限を1024×1024と設定したのですが、それよりも小さい迷路であってもSegmentation faultが出てしまいます。入力となる迷路データは別にtxt形式で保存し実行の際に読み込ませています。メインのソースコードのファイル名がq3-5.cであり読み込ませる迷路データのファイル名がq3-mazeex5.txtとしています。

発生している問題・エラーメッセージ

$ gcc -std=c99 -o  q3-5 q3-5.c
$ ./q3-5 < q3-mazeex5.txt
$ Segmentation fault

該当のソースコード

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_MAZE_SIZE 1024
#define NUMBER_OF_DIRECTIONS 4 // left, right, up, down

enum { FORWARD, BACKWARD };
typedef int bool;
typedef struct { int i, j; } position;
typedef struct {
  int size_row, size_col;
  char map [ MAX_MAZE_SIZE ][ MAX_MAZE_SIZE ];
  position start, goal;
} maze;

///////////////////////////////////////////////////////////////////////////////
// Stack definition
///////////////////////////////////////////////////////////////////////////////
#define STACKSIZE MAX_MAZE_SIZE
typedef position elementtype;

typedef struct {
  int top;
  elementtype elements[STACKSIZE];
} stack;

void initstack(stack *s)
{
  s->top = -1;
}

int stackempty(stack *s)
{
  return (s->top < 0);
}

void printstack(stack *s)
{
  printf("[");
  for(int i = 0; i <= s->top; i++){
    printf("(%d,%d)", s->elements[i].i, s->elements[i].j);
    if (i < s->top) {
      printf(", ");
    }
  }
  printf("]\n");
}

void push(stack *s, elementtype x, char c)
{
  s->top += 1;
  if (s->top >= STACKSIZE) {
    printf("Stack overflow.\n"); exit(1);
  } else {
    s->elements[s->top] = x;
  }
  printf("%c push (%d,%d): ", c, x.i, x.j);
  printstack(s);
  return;
}

elementtype pop(stack *s, char c)
{
  elementtype x;
  if (s->top < 0){
    printf("%c Stack is empty.\n", c); exit(1);
  } else {
    x = s->elements[s->top];
    s->top -= 1;
    printf("%c pop: (%d,%d), ", c, x.i, x.j);
    printstack(s);
    return x;
  }
}
///////////////////////////////////////////////////////////////////////////////

position possible_moves [ 4 ] = {
  { .i =  0, .j = -1 },
  { .i =  0, .j = +1 },
  { .i = -1, .j =  0 },
  { .i = +1, .j =  0 } };
position move ( position p, position d ) { position q = { .i = p.i + d.i, .j = p.j + d.j }; return q; }
bool equal ( position p, position q ) { return ( p.i == q.i && p.j == q.j ) ? 1 : 0; }

void read_maze ( maze *m )
{
  char str [ MAX_MAZE_SIZE + 2 ]; // +2 = '\n' + '\0'
  position p = { .i = 0, .j = 0 };

  while ( fgets ( str, MAX_MAZE_SIZE + 2, stdin ) ) {
    for (p.j = 0; str [ p.j ] != '\n'; p.j++ ) {
      m->map [ p.i ][ p.j ] = str [ p.j ];
      if ( str [ p.j ] == 'S' ) {
        m->start = p;
      }
      if ( str [ p.j ] == 'G' ) {
        m->goal = p;
      }
    }
    p.i += 1;
  }
  m->size_row = p.i;
  m->size_col = p.j;
}

void print_maze ( maze m )
{
  position a;

  printf(" ");
  for ( int j = 0; j < m.size_col; j++ ) {
    printf("%d", j%10);
  }
  printf("\n");

  for ( a.i = 0; a.i < m.size_row; a.i++ ) {
    printf("%d", a.i%10);
    for ( a.j = 0; a.j < m.size_col; a.j++ ) {
      printf ( "%c", m.map [ a.i ][ a.j ] );
    }
    printf ( "\n" );
  }
}

bool is_in ( maze *m, position p ) { return ( 0 <= p.i && p.i <= m->size_row - 1 && 0 <= p.j && p.j <= m->size_col - 1 ) ? 1 : 0; }
bool is_goal ( maze *m, position p ) { return ( m->map [ p.i ][ p.j ] == 'G' ) ? 1 : 0; }
bool is_wall ( maze *m, position p ) { return ( m->map [ p.i ][ p.j ] == '#' ) ? 1 : 0; }
int next_possible_move ( maze *m, position cur, position prev, position candidate [] )
{
  int n = 0;
  for ( int i = 0; i < NUMBER_OF_DIRECTIONS; i++ ) {
    position next = move ( cur, possible_moves [ i ] );
    if ( is_in ( m, next ) && ! is_wall ( m, next ) && ! equal ( next, prev ) ) { candidate[n] = next; n += 1; }
  }
  return n;
}

void solve ( maze *m )
{
  position start = m->start;
  position goal  = m->goal;
  stack route, branch;
  position cur, next, prev;
  position candidate [ NUMBER_OF_DIRECTIONS ]; // left, right, up, down;
  bool direction = FORWARD;

  initstack ( &route );
  initstack ( &branch );

  prev = start;
  cur = start;
  int n = next_possible_move ( m, cur, prev, candidate ); // 次の可能な移動を検索
  push ( &route, cur, 'r' );
  cur = candidate [ 0 ];

  printf("START\n");
  while(! is_goal ( m, cur ) ) { // ゴールに到達するまで繰り返し
    printf("CUR: (%d,%d)\n", cur.i, cur.j);
    n = next_possible_move ( m, cur, prev, candidate ); // 次の可能な移動を検索
    prev = cur;
    switch ( n ) {

case 0: // 行き止まり
      if (stackempty(&branch))
      {
        printf("No solution found.\n");
        return;
      }
      direction = BACKWARD;
      cur = pop(&route, 'r'); // 逆戻り
      printf("%s\n", (direction == FORWARD) ? "FORWARD" : "BACKWARD");
      break;

    case 1: // 一本道
      if (direction == FORWARD)
      {
        push(&route, cur, 'r');
        cur = candidate[0];
      }
      else
      {
        cur = pop(&route, 'r');
      }
      printf("%s\n", (direction == FORWARD) ? "FORWARD" : "BACKWARD");
      break;

    default: // 分岐
      printf("BRANCH\n");
      if(direction == FORWARD){
        push(&route, cur, 'r');
      for (int i = 0; i < n; i++){
        next = candidate[i];
        if(!is_wall(m, next)){
        push(&branch, next, 'b');
        }
      } 
        cur = pop(&branch, 'b');
      }
      else{
          cur = pop(&branch, 'b');
          direction = FORWARD;
      }
      
      printf("%s\n", (direction == FORWARD) ? "FORWARD" : "BACKWARD");
      break;
    }
  }


  // ゴールに到達した
  // 行儀悪いけど、構造体の内容を書き換えて経路を追加
  printf("DONE\n");
  while ( 1 ) {
    cur = pop ( &route, 'r' );
    if ( equal ( cur, start ) ) { break; }
    m->map [ cur.i ][ cur.j ] = '.';
  }

}

int main(void)
{
  maze m;

  read_maze ( &m );

  solve ( &m );

  print_maze ( m );

  return 0;
}

#############################
##############S##############
############## ##############
####### ###### ###### #######
######                 ######
####### ###### ###### #######
############## ##############
####### ###### ###### #######
####       ### ###       ####
####### ###### ###### #######
####### ###### ###### #######
####       ### ###       ####
####### ###### ###### #######
####### ###### ###### #######
####### ###### ###### #######
#                           #
####### ###### ###### #######
####### ###### ###### #######
####### ###### ###### #######
####       ### ###     G ####
####### ###### ###### #######
####### ###### ###### #######
####       ### ###       ####
####### ###### ###### #######
############## ##############
####### ###### ###### #######
######                 ######
####### ###### ###### #######
#############################

試したこと

gdbを用いてデバッグしたところ、上のソースコードの93行目に問題があると表示されました。
しかしこの部分のどこに問題があるのかわかりません。

補足情報（FW/ツールのバージョンなど）

gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

Comments

[int32_t]

> 上のソースコードの93行目に問題がある

クラッシュしたときに p.i と p.j の値はどうなってましたか?

[Tsuruha]

(gdb) p p.i
$1 = 28
(gdb) p p.j
$2 = 1026248
のように表示されました。当方gdbに慣れておらず質問に答えられているかわかりませんがよろしくお願いいたします。

[int32_t]

p.j の値がおかしいように見えますね。
実行するときに標準入力にどんなデータを与えていますか。

[jimbe]

データもご提示ください。
93行目ということは迷路データの取り込みで失敗しているので迷路を探索するに至っていないということでしょう。
問題が起きる時の p.i が 28 なのだとしたら、迷路データの 29行(?)目に問題があると見るべきでしょう。

[Tsuruha]

申し訳ありません。入力を提示していませんでした。入力も併せて確認できるように更新いたしましたのでよろしくお願いいたします。

[jimbe]

入力の29行目の後に改行は入っているでしょうか。

fgets はストリームが EOF になった場合も戻ります。データの最後に改行が入っていなければ当然配列にも改行は入らず、93行目の書き方ではループが終わりません。
行毎の処理であれば改行コードでデータの終わりを判定するのではなく、基本は ヌル文字('\0')が現れるまで、もしくは strlen 関数でバイト数を得てその数だけ処理するようにし、有ったり無かったりする改行はそのような処理する前に「有ったら削除しておく」ようにするのが妥当ではないでしょうか。

[Tsuruha]

改行は入っていません。改行を入れて実行したところ、スタックがオーバーフローしエラーが出てしまいました。実行例として改行がない場合にも正しく動作するためにはどのようにすれば良いのでしょうか？

Answer 1

  while ( fgets ( str, MAX_MAZE_SIZE + 2, stdin ) ) {
    for (p.j = 0; str [ p.j ] != '\n'; p.j++ ) {

ファイルの最後の行が \n で終わっていない場合、このコードは読み込んだデータの終端を通り越してクラッシュします。
\0 もチェックするとか、fgets() で読み込んだ直後に最後の \n を \0 に書き換えて \0 の存在をチェックするのが常套手段です。

  while (fgets(str, MAX_MAZE_SIZE + 2, stdin)) {
    for (p.j = 0; str[p.j] != '\n' && str[p.j]; p.j++) {

  while (fgets(str, MAX_MAZE_SIZE + 2, stdin)) {
    size_t len = strlen(str);
    if (str[len - 1] == '\n')
      str[len - 1] = '\0';
    for (p.j = 0; str[p.j]; p.j++) {

改行を入れて実行したところ、スタックがオーバーフローしエラーが出てしまいました。

それは当初の質問とは別問題なので、別の質問を立てたほうがよいでしょう。