Recording a maze path solution with a stack

I am to generate a solution to a maze using a linked list implementation of a stack in some way. The maze is read in from a .txt file and consists of 0's for open spaces and 1's for walls. <- Pretty sure an exit must be in the bottom row? So those three 0's?

The algorithm I am attempting to use is:

While Not At End
    If Can Go North
        Go North
    ElseIf Can Go East
        Go East
    ElseIf Can Go South
        Go South
    ElseIf Can Go West 
        Go West
    EndIf
Wend

The way I've been attempting it relied on the ++ operations executing within an array index. I was unaware the array subscript operator [ took precedence over ++ so now I need to rethink a work around. Before doing so, I want to make sure this method will even work in first place. Could anyone take a look at my algo code thus far and provide some feed back? (Note: I still need to add in some code to track paths taken to avoid some type of infinite loop)

bool notSolved = true;
        int path = 0;
        row = 0;
        col = 0;

        rowStack.push(row);
        colStack.push(col);

        while (notSolved){

        //(from perspective of person looking at maze on screen)
        if (maze[row--][col] == 0){//if you can go up, go up
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row][col++] == 0){//else if you can go right, go right
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row++][col] == 0){//else if you can go down, go down
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row][col--] == 0){//else if you can go left, go left
        rowStack.push(row);
        colStack.push(col);
        path++;
        }

            if((maze[row][col] == 0) && (row == (size - 1))){//if we reached an exit
                cout << "Solution Path:" << endl;
                for (int i = 0; i < path; i++){
                    cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl;
                    rowStack.pop();
                    colStack.pop();
                }
            notSolved = false;
            }
        }

Problem with executing [ before ++:

Any help appreciated, Thanks!

Answers


Your algorithm will not work in certain mazes that have circular paths: once you get into one of these, you'll be going in circles. To fix this, you need to add a boolean array visited[R][C][DIR], where DIR is a number from zero to three representing a direction. When you leave cell [r][c] in the direction [d], set visited[r][c][d] to true. Next time you visit the same cell, see if you have left it in the same direction before; if you did, skip that direction, and go for the next one down the line.


Need Your Help

respond_to? complains about nil is not a symbol

ruby metaprogramming

I'm writing a CLI tool and have the following code:

Polygon shape does not show up in Java

java eclipse swing drawing paintcomponent

I'm trying to make some shapes with Java, I created two rectangles and they show up normally, but lately I integrated a polygon shape code but it not showing up while running the program. Somebody ...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.