0

私のプログラムでこの小さな問題が発生しています。Visual Studio 2012 では正常に動作しますが、G++ でコンパイルすると (上記の理由により、コンパイルに使用する必要があります)、入力に応じてエラー信号 11(SIGSEGV) または 6(SIGABRT) がトリガーされます。 . これはプログラミングの演習であり、10 の異なる入力で私のプログラムをテストする別のプログラム (オンライン サーバー上) があります。前述のとおり、Visual Studio 2012 を使用している間、プログラムはコンパイルされ、正常に動作します。

プログラムについて: 開始点 (x,y) からいくつかの出口までの最短経路を見つけます (出口の数は無関係であり、異なります。出口が 1 つだけの場合もあれば、200 の場合もあります)。入力は次のようになります。

7 12          // maze height and width
##########.#  //
#..........#  //
#.###.######  //
#..X#.#.....  // the maze blueprint
#.###.#.####  //
#..........#  //
############  //

そして私のプログラム：

#include <iostream>
#include <vector>

typedef struct _laby_t {
    int h, w;
    char **pohja; // 'pohja' is finnish and means layout
} laby_t;

typedef std::vector<int> monovector;
typedef std::vector< std::vector<int> > bivector;

laby_t *laby_allocate (int r, int c)
{
    laby_t *laby;
    int i;

    laby = new laby_t[sizeof (laby_t)];
    laby->pohja = new char *[r];
    for (i = 0; i < r; i++)
    {
        laby->pohja[i] = new char[c];
    }
    laby->h = r;
    laby->w = c;

    return laby;
}

int wander(int y, int x, laby_t *&_laby, int goals)
{
    laby_t *laby = _laby;
    int found = 0, depth = 0, min_path = 1000000;
    bool b = 0;
    bivector openList;
    monovector start; start.push_back(y); start.push_back(x);
    bivector closedList;

    openList.push_back(start);

    while(found < goals)
    {

        y = openList.back()[0]; x = openList.back()[1];
        monovector r; r.push_back(y); r.push_back(x); closedList.push_back(r);
        openList.pop_back();
        if(laby->pohja[y][x] != '*') laby->pohja[y][x] = '-';
        depth++;

        if(y == 0 || y+1 == laby->h || x == 0 || x+1 == laby->w) {
            found++;
            if(depth < min_path) min_path = depth;
            if(found >= goals) {
                std::cout << min_path << std::endl;
                break;
            }
            laby->pohja[y][x] = '-';

            goto back_track;
        }
        else
        {
            b = 0;
            if(laby->pohja[y+1][x  ] == '.') { monovector r; r.push_back(y+1); r.push_back(x); openList.push_back(r); b=1; }
            if(laby->pohja[y  ][x+1] == '.') { monovector r; r.push_back(y); r.push_back(x+1); openList.push_back(r); b=1; }
            if(laby->pohja[y-1][x  ] == '.') { monovector r; r.push_back(y-1); r.push_back(x); openList.push_back(r); b=1; }
            if(laby->pohja[y  ][x-1] == '.') { monovector r; r.push_back(y); r.push_back(x-1); openList.push_back(r); b=1; }
            if(!b)
            {
back_track:     while(closedList.size() > 0)
                {
                    //std::cout << closedList.size() << std::endl;
                    int c_y = closedList.back()[0]; int c_x = closedList.back()[1];
                    int o_y = openList.back()[0];   int o_x = openList.back()[1];

                    laby->pohja[y][x] = '*';

                    y = c_y; x = c_x;

                    laby->pohja[y][x] = '*';

                    if( (c_y+1 == o_y && c_x   == o_x) ||
                        (c_y   == o_y && c_x+1 == o_x) ||
                        (c_y-1 == o_y && c_x   == o_x) ||
                        (c_y   == o_y && c_x-1 == o_x) )
                    {
                        laby->pohja[y][x] = '-';
                        y = o_y; x = o_x;
                        closedList.pop_back();
                        depth--;
                        break;
                    }
                    else {
                        closedList.pop_back();
                        depth--;
                    }
                }
            }
        }
    }

    return min_path;
}

int main()
{
    int h, w, goals = 0;
    std::cin >> h >> w;

    laby_t *laby;
    laby = laby_allocate(h, w);

    for(int i = 0; i < laby->h; i++)
        std::cin >> laby->pohja[i];

    for(int i = 1; i < laby->h-1; i++) {
        if(laby->pohja[i][0] == '.') goals++;
        if(laby->pohja[i][laby->w-1] == '.') goals++;
    }

    for(int i = 1; i < laby->w-1; i++) {
        if(laby->pohja[0][i] == '.') goals++;
        if(laby->pohja[laby->h-1][i] == '.') goals++;
    }

    for(int i = 0; i < laby->h; i++)
        for(int j = 0; j < laby->w; j++) {
            if(laby->pohja[i][j] == 'X') {
                wander(i, j, laby, goals);
                goto _exit;
            }
        }

_exit:

    //system("pause");
    return 0;
}

私はエラーシグナルに関する宿題をしました。皆さんがそれについて知らない場合のために: http://www.yolinux.com/TUTORIALS/C++Signals.html

前もって感謝します。

4

2 に答える 2

5

このコードは、G++ 4.7.1 を使用する Mac OS X 10.7.5 で問題なくコンパイルされます。

g++ -g -Wall -Wextra laby.cpp -o laby

残念ながら、結果を の下valgrindで実行すると、次のようになります。

==15030== Invalid write of size 1
==15030==    at 0x306BE: std::basic_istream<char, std::char_traits<char> >& std::operator>><char, std::char_traits<char> >(std::basic_istream<char, std::char_traits<char> >&, char*) (in /usr/lib/libstdc++.6.0.9.dylib)
==15030==    by 0x10000117D: main (laby.cpp:113)
==15030==  Address 0x10001632c is 0 bytes after a block of size 12 alloc'd
==15030==    at 0xB823: malloc (vg_replace_malloc.c:266)
==15030==    by 0x5768D: operator new(unsigned long) (in /usr/lib/libstdc++.6.0.9.dylib)
==15030==    by 0x576DA: operator new[](unsigned long) (in /usr/lib/libstdc++.6.0.9.dylib)
==15030==    by 0x1000008C0: laby_allocate(int, int) (laby.cpp:21)
==15030==    by 0x100001146: main (laby.cpp:110)

そのため、関数のメモリ割り当てに問題がありlaby_allocate()ます。それとも数...

laby_t *laby_allocate (int r, int c)
{
    laby_t *laby;
    int i;

    laby = new laby_t[sizeof (laby_t)];

laby_tこの行は;の配列を割り当てます。にあるバイトと同じ数の要素を配列に割り当てますlaby_t。これはあなたが必要としていたものではありません。

    laby = new laby_t;

続き:

    laby->pohja = new char *[r];
    for (i = 0; i < r; i++)
    {
        laby->pohja[i] = new char[c];
    }

これは、データの最後にあるヌルに十分なスペースを割り当てません...これが、「書き込み」が1バイトである理由です。を変更しcて、きれいな健康状態を示しますc+1。valgrind

    laby->h = r;
    laby->w = c;

    return laby;
}

与えられた答えは次のとおりです15。それが正しいとは確信していません。

于 2012-12-29T17:40:53.920 に答える
2

この行は、メモリ割り当てをオーバーフローします。ユーザーがw文字を入力した場合、nullで終了する文字列を保持するには（w + 1）文字が必要になります。

    std::cin >> laby->pohja[i];

laby_tこの行は、1つだけが必要なように見えますが、多くのオブジェクトの配列も割り当てています。おそらく、C++newとCを混同しているでしょうmalloc。

laby = new laby_t[sizeof (laby_t)];

これに置き換えることができます。

laby = new laby_t;

これもCの残骸のようです。これはバグではありませんが、現在の名前空間を冗長なシンボルで不必要に汚染します。

typedef struct _laby_t { ... } laby_t;

これに置き換えることができます。

struct laby_t { ... };
于 2012-12-29T17:30:20.150 に答える