Address boundry error while using STL in C++

Question

I was writing the program for finding a path through an defined matrix.

#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();
}

This program works fine for most of the inputs. But gives an address boundry error for the following input

Enter rows and colums: 4 4

ENter initial configuration (1 for block, 0 for open):0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0

Enter initial state in row column:1 0

Enter final state in row column:3 3 fish: “./a.out” terminated by signal SIGSEGV (Address boundary error)

Please suggest the possible reason for this error and how to correct it

Answer 1

I realized where the mistake was. I did not initialize x and y in the functions maze::up(), maze::down(), maze::right() and maze::left() as it was always supposed to be initialized by the function while traversing the matrix. The Error was in the algorithm itself. The variable curr from state_search() was supposed to denote the depth of the BFS tree. But since it was incrementing for every node found, it denoted the depth wrongly causing error whenever there were 2 possible paths.

To solve this issue, I removed the curr variable from state_search() and added it to the class definition initializing it to 1 and incrementing it whenever the functions maze::up(), maze::down(), maze::right() and maze::left() are called.

here is the complete working code

#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();
    }

Answer 2

The problem is that you don't initialize x and y values in your up, down, left and right functions. And then if you don't find the indexes for curr, you access the inst array at random indexes.

In right function you should declare x and y like this:

int x = 0,y = 0;

In left:

int x = m - 1,y = 0;

Do the same in right and left.

Answer 3

You use uninitialized variables x and y in method maze::up:

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

So when in following loops we didn't go inside if statement these variables still contain garbage from uninitialized allocated memory.

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

And it's very high possibility that x is not in range [0, 10).

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

And we immediately try to get value somewhere (inst[x-1][y]) far away in memory, and terminated with segmentation error.

---

Fix: It's better to initialize all the variables with meaningful values. Suppose that for your code this is correct solution:

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

You can tell to compiler to notify you when you keep somewhere uninitialized variables.

If you use GCC compiler you can use compilation flag:

g++ -O2 -Wuninitialized prog.cpp

And you will see a lot of similar places in your code. Additionally you can use flag -Wall, and you will found that bool state_search() function reaches end without returning any value.