0

我正在编写通过定义矩阵查找路径的程序。

#include<iostream>
#include<list>

using namespace std;

class maze{
    int inst[10][10];
    int m,n,initr,initc,finalr,finalc;
public:
    maze(int c){
        if(c==1) return;
        cout<<"\n Enter rows and colums: ";
        cin>>m>>n;
        cout<<endl<<"\n ENter initial configuration (1 for block, 0 for open):";
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin>>inst[i][j];
            }
        }
        cout<<endl<<"Enter initial state in row column:";
        cin>>initr>>initc;
        cout<<endl<<"Enter final state in row column:";
        cin>>finalr>>finalc;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==1) inst[i][j]=(-1);
            }
        }
        inst[initr][initc]=1;
    }
    bool up(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        if(x==0) return false;
        if(inst[x-1][y]==0){
            //cout<<"\n up "<<x-1<<y; 
            inst[x-1][y]=curr+1;
            return true;
        }else return false;

    }
    bool down(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        if(x==m-1) return false;
        if(inst[x+1][y]==0){
            //cout<<"\n down "<<x+1<<y;
            inst[x+1][y]=curr+1;
            return true;
        }else return false;

    }
    bool left(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        if(y==0) return false;
        if(inst[x][y-1]==0){
            //cout<<"\n left "<<x<<y-1;
            inst[x][y-1]=curr+1;
            return true;
        }else return false;

    }
    bool right(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }

        if(y==n-1) return false;
        if(inst[x][y+1]==0){
            //cout<<"\n right "<<x<<y+1;
            inst[x][y+1]=curr+1;
            return true;
        }else return false;

    }
    bool check(int curr){
        int x,y;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inst[i][j]==curr) {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        if(x==finalr && y==finalc) return true;
        else return false;
    }   
    void print_maze(){
        cout<<endl<<endl;
        for(int i=0;i<m;i++){
            cout<<endl;
            for(int j=0;j<n;j++){
                cout<<"\t"<<inst[i][j];
            }
        }
    }

};

bool state_search(){
    int curr=1;
    maze start(0),temp(1);
    list<maze> queue;

    queue.push_back(start);
    while(!queue.empty()){
        start = queue.front();
        queue.pop_front();
        if(start.check(curr)){
            start.print_maze();
            return true;
        }
        //start.print_maze();

        temp=start;
        if(temp.up(curr)) queue.push_back(temp);

        temp=start;
        if(temp.down(curr)) queue.push_back(temp);

        temp=start;
        if(temp.left(curr)) queue.push_back(temp);

        temp=start;
        if(temp.right(curr)) queue.push_back(temp);

        curr++;
    }
    cout<<"\n No answer found";
}


int main(){
    state_search();
}

该程序适用于大多数输入。但给出以下输入的地址边界错误

输入行和列：4 4

ENter初始配置（1表示块，0表示打开）：0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0

在行列中进入初始状态：1 0

在行列中输入最终状态：3 3 鱼：“./a.out”由信号 SIGSEGV 终止（地址边界错误）

请提出此错误的可能原因以及如何纠正它

4

3 回答 3

1

问题是您没有在 up、down、left 和 right 函数中初始化x和y值。然后，如果您没有找到 curr 的索引，您可以在随机索引处访问inst数组。

在正确的函数中，您应该像这样声明 x 和 y：

int x = 0,y = 0;

在左边：

int x = m - 1,y = 0;

在right和left做同样的事情。

于 2016-02-15T08:07:19.507 回答
0

您使用未初始化的变量x和y方法maze::up：

bool up(int curr){
    int x,y; // !!!
    ...

因此，当在后续循环中我们没有进入if语句内部时，这些变量仍然包含来自未初始化分配内存的垃圾。

    ...
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(inst[i][j]==curr) {
                x=i;
                y=j;
                break;
            }
        }
    }
    ...

而且很有可能x不在 [0, 10) 范围内。

    ...
    if(x==0) return false;
    if(inst[x-1][y]==0){
    ...

我们立即尝试inst[x-1][y]在内存中远处某处（）获取值，并以分段错误终止。

修复：最好用有意义的值初始化所有变量。假设对于您的代码，这是正确的解决方案：

bool up(int curr){
    int x = 0, y = 0;
    ...

当您将未初始化的变量保存在某个地方时，您可以告诉编译器通知您。

如果您使用 GCC 编译器，则可以使用编译标志：

g++ -O2 -Wuninitialized prog.cpp

你会在你的代码中看到很多类似的地方。此外，您可以使用 flag -Wall，您会发现该bool state_search()函数在没有返回任何值的情况下结束。

于 2016-02-15T08:39:04.723 回答
0

我意识到错误在哪里。我没有在函数中初始化x和，因为在遍历矩阵时它总是应该由函数初始化。错误在算法本身。变量from应该表示 BFS 树的深度。但由于它为找到的每个节点而递增，因此只要有 2 条可能的路径，它就表示深度错误地导致错误。ymaze::up()maze::down()maze::right()maze::left()currstate_search()

为了解决这个问题，我curr从类定义中删除了变量state_search()并将其添加到类定义中，将其初始化为 1，并在函数、maze::up()和被调用时将其递增。maze::down()maze::right()maze::left()

这是完整的工作代码

#include<iostream>
    #include<list>

    using namespace std;

    class maze{
        int inst[10][10];
        int m,n,initr,initc,finalr,finalc,curr;
    public:
        maze(int c){
            if(c==1) return;
            cout<<"\n Enter rows and colums: ";
            cin>>m>>n;
            cout<<endl<<"\n ENter initial configuration (1 for block, 0 for open):";
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    cin>>inst[i][j];
                }
            }
            cout<<endl<<"Enter initial state in row column:";
            cin>>initr>>initc;
            cout<<endl<<"Enter final state in row column:";
            cin>>finalr>>finalc;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==1) inst[i][j]=(-1);
                }
            }
            inst[initr][initc]=1;
            curr=1;
        }
        bool up(){
            int x=0,y=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }
            if(x==0) return false;
            if(inst[x-1][y]==0){
                inst[x-1][y]=curr+1;
                curr++;
                return true;
            }else return false;

        }
        bool down(){
            int x=m-1,y=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }
            if(x==m-1) return false;
            if(inst[x+1][y]==0){
                inst[x+1][y]=curr+1;
                curr++;
                return true;
            }else return false;

        }
        bool left(){
            int x,y=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }
            if(y==0) return false;
            if(inst[x][y-1]==0){
                inst[x][y-1]=curr+1;
                curr++;
                return true;
            }else return false;

        }
        bool right(){
            int x,y=n-1;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }

            if(y==n-1) return false;
            if(inst[x][y+1]==0){
                inst[x][y+1]=curr+1;
                curr++;
                return true;
            }else return false;

        }
        bool check(){
            int x,y;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(inst[i][j]==curr) {
                        x=i;
                        y=j;
                        break;
                    }
                }
            }
            if(x==finalr && y==finalc) return true;
            else return false;
        }   
        void print_maze(){
            cout<<endl<<endl;
            for(int i=0;i<m;i++){
                cout<<endl;
                for(int j=0;j<n;j++){
                    cout<<"\t"<<inst[i][j];
                }
            }
        }

    };

    bool state_search(){

        maze start(0),temp(1);
        list<maze> queue;

        queue.push_back(start);
        while(!queue.empty()){
            start = queue.front();
            queue.pop_front();
            if(start.check()){
                start.print_maze();
                return true;
            }

            temp=start;
            if(temp.up()) queue.push_back(temp);

            temp=start;
            if(temp.down()) queue.push_back(temp);

            temp=start;
            if(temp.left()) queue.push_back(temp);

            temp=start;
            if(temp.right()) queue.push_back(temp);
        }
        cout<<"\n No answer found";
        return false;
    }


    int main(){
        state_search();
    }
于 2016-02-15T11:25:29.953 回答