This is a "personal project".

[jumper007]

I am trying to figure out an "algorithm" for finding the shortest path in a given matrix (2D array). The data given is being read from file. On the first line, I am giving the number of lines (the variable's name is 'lin') and the number of columns (the variable's name is 'col') that the matrix will have.
On the following 'lin' lines and 'col' columns I am giving the matrix following these rules:
- A "point" may be a part of the path if the value of that "point" (path[i][j]) is equal to '0 (zero)'.
- A "point" cannot be a part of the path if the value of that "point" (path[i][j]) is equal to '1'.
In this program, I am trying to find the shortest path knowing that the starting point will always be 'path[1][1]' and the ending point will be 'path[lin][col]'.
I know that my code can be a lot more improved and it won't work for any given matrix, but I am getting a

Program received signal SIGSEGV, Segmentation fault.

So, with all these being said, here is my code:

#include <iostream>
#include <fstream>

const int Max = 1001;

using namespace std;

void readPath(int path[Max][Max], int &lin, int &col);
void borderPath(int path[Max][Max], int lin, int col);
int checkPath(int path[Max][Max], int x, int y);

int main(int argc, char* argv[])
{
    int path[Max][Max];
    int lin = 0; // initializing number of lines
    int col = 0; // initializing number of columns
    int k = 0, i = 1, j = 1; // k - the length of the path; i - the current line; j - the current column.

    readPath(path,lin,col);
    borderPath(path,lin,col);

    do
    {
        if (checkPath(path,i+1,j+1) == 1)
        {
            i++; j++; k++; path[i][j] = -1;
        }
        else
        {
            if (checkPath(path,i+1,j) == 1)
            {
                i++; k++; path[i][j] = -1;
            }
            else
            {
                if (checkPath(path,i+1,j-1) == 1)
                {
                    i++; j--; k++; path[i][j] = -1;
                }
                else
                {
                    if (checkPath(path,i,j+1) == 1)
                    {
                        j++; k++; path[i][j] = -1;
                    }
                    else
                    {
                        if (checkPath(path,i,j-1) == 1)
                        {
                            j--; k++; path[i][j] = -1;
                        }
                        else
                        {
                            if (checkPath(path,i-1,j+1) == 1)
                            {
                                i--; j++; k++; path[i][j] = -1;
                            }
                            else
                            {
                                if (checkPath(path,i-1,j) == 1)
                                {
                                    i--; k++; path[i][j] = -1;
                                }
                                else
                                {
                                    if (checkPath(path,i-1,j-1) == 1)
                                    {
                                        i--; j--; k++; path[i][j] = -1;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

    }while(i != lin && j != col);

    cout << "The shortest path found has the length: " << k << ".\n";

    return 0;
}

void readPath(int path[Max][Max], int &lin, int &col)
{
    ifstream _inFILE("path.txt");

    _inFILE >> lin >> col;

    for (int i = 1; i <= lin; i++)
    {
        for (int j = 1; j <= col; j++)
        {
            _inFILE >> path[i][j];
        }
    }
}

void borderPath(int path[Max][Max], int lin, int col)
{
    for (int i = 0; i <= lin+1; i++)
    {
        path[i][0] = path[i][col+1] = 1;
    }
    for (int j = 0; j <= col+1; j++)
    {
        path[0][j] = path[lin+1][j] = 1;
    }
}

int checkPath(int path[Max][Max], int x, int y)
{
    if (path[x][y] == 0)
        return 1;
    else
        return 0;
}

Any help would be highly appreciated. Thanks.

[Moschops]

Run it under a debugger.

http://www.cplusplus.com/articles/iwTbqMoL/

[TheIdeasMan]

Here's an idea for checking the adjacent cells in a matrix, which is what I think you are doing with that nightmare do loop in main:

1. Start from [1][1] and end at [SIZE-1][SIZE-1] so the next part doesn't fail
2. have nested for loops to increment Row and Col
3. Start from [Row-1][Col-1], using nested for loops to test a 3 by 3 matrix.
4. Skip the [1][1] in the 3 by 3 matrix as this is the current cell.
5. Have logic to decide the direction of movement, get a new Row and Col, update path length etc.
6. Do steps 3 to 5 again.

Steps 3 to 5 should be in it's own function.

Have a go at this -could improve your code a lot.

Cheers.

[TheIdeasMan]

Just saw this part:

void borderPath(int path[Max][Max], int lin, int col)
{
    for (int i = 0; i <= lin+1; i++)

Does the debugger show a problem here?

[jumper007]

Thanks for the answers. I will try to do that and if any issues occur, I will come back here.
By the way, the segmentation fault was because of the huge declaration I had given (an 1001x1001 array).

EDIT: No, it doesn't. That part works alright. I have tested it as a stand-alone program and it does its job.

[TheIdeasMan]

You have run the debugger already?

The code snippet I posted could be a problem if lin == Max because it would go past the array by 2.

[jumper007]

Yes, I did and I know what you mean, but I don't intend to use any values close to Max, at least not yet. For now, I am trying to make it work with small values.

My basic, maybe too easy, example was:

5 4
0 1 0 0
0 0 0 1
0 1 0 0
0 0 1 1
0 0 0 0

Which means, 5 lines, 4 columns, and the given matrix. The shortest path should be returned as 5.

[TheIdeasMan]

This is actually quite a tricky problem - basically a maze solving problem.

The thing is, what to do when come to a dead end. Answer is to go back to the last place there were options for which direction to go in ( a decision point), and try from there, if that eventually fails, keep going back to previous decision points.

Also there could be multiple solutions, need to find all of them and see which is shortest.

Starting out small & simple is a really good strategy.

Any way, best of luck - hope all goes well.

[jumper007]

Thank you. I really appreciate all of your help.