开发者

Stack based exploration of maze

开发者 https://www.devze.com 2023-02-08 12:09 出处:网络
I\'m trying to write a simple C++ program to fill a maze with distances from the starting point, but am failing.

I'm trying to write a simple C++ program to fill a maze with distances from the starting point, but am failing.

And the code is:

/*I'm trying to write a simple C++ program to fill a maze with distances from the starting point, but am failing. 

The pseudocode for the function is

 Set every element of the distance array to 99.
        Set position (sr,sc) of the distance array to 0.
        Push the starting coordinate (sr,sc) onto the coordinate stack.
        While the stack is not empty,
        {   Pop the top coordinate off the stack. This gives you the current
                (r,c) location that your algorithm is exploring.
            Let m be the minimum of the values of the four neighbors of (r,c)
                in the distance array.  If the value at (r,c) in the distance
                array is greater than m+1, then set it to m+1.
            Let v be the value at (r,c) in the distance array.
            Check where you can move from the current position:
                If you can move NORTH and the value at position (r-1,c) in the
                    distance array is greater than v+1, then set it to v+1 and
                    push (r-1,c) onto the coordinate stack.
                If you can move EAST and the value at position (r,c+1) in the
                    distance array is greater than v+1, then set it to v+1 and
                    push (r,c+1) onto the coordinate stack.
                If you can move SOUTH and the value at position (r+1,c) in the
                    distance array is greater than v+1, then set it to v+1 and
                    push (r+1,c) onto the coordinate stack.
                If you can move WEST and the value at position (r,c-1) in the
                    distance array is greater than v+1, then set it to v+1 and
                    push (r,c-1) onto the coordinate stack.

And the code is
*/
//#include "StdAfx.h"
#include <stack>
#include<iostream>
#include <iomanip>
using namespace std;
class Coord
{
public:
Coord(int rr, int cc) : m_r(rr), m_c(cc) {}
int r() const { return m_r; }
int c() const { return m_c; }
private:
int m_r;
int m_c;
};
int minimum(int a[],int size)
{
    int small=a[0];
    for(int i=0;i<size;i++)
        if(a[i]<small)
            small=a[i];
    return small;
}

void determineDistances(const char maze[][10], int sr, int sc, int dist[][10])
{
    stack<Coord> coordStack; //from HW spec
    coordStack.push(Coord(sr,sc));
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
        {
            dist[i][j]=99;
        }
        dist[sr][sc]=0;
        int distarr[4];                     //      Array to hold up, down, left, right values
        int min;
        int currval;                        //      Current value in dist[][10] array
        while (!coordStack.empty())
        {
            Coord inuse = coordStack.top();
            coordStack.pop();               //      Pop the top coordinate off the stack
            const int row = inuse.r();          //      Assigning row value
            const int col = inuse.c();          //      Assigning col value
                                            //      (row,col) location that your algorithm is exploring
            cout<<"test row "<<row<<" col "<<col<<endl;
            distarr[0]=dist[row-1][col];    //      Up
            distarr[1]=dist[row+1][col];    //      Down
            distarr[2]=dist[row][col-1];    //      Left
            distarr[3]=dist[row][col+1];    //      Right
            min=minimum(distarr,4);         //      Let max be the minimum of the values of the four neighbors of (r,c)
                                            //      in the distance array
            if(dist[row][col]>min+1)        //      If the value at (r,c) in the distance
            dist[row][col]=min+1;           //      array is gre开发者_JS百科ater than m+1, then set it to m+1.
            currval=dist[row][col];     
            if ((maze[row-1][col] == '.')&&(dist[row-1][col]>(currval+1)))
             {
            dist[row-1][col]=currval+1;
            coordStack.push(Coord(row+1,col));
             } 
             if (maze[row+1][col] == '.'&&(dist[row+1][col]>(currval+1)))
             {
            dist[row+1][col]=currval+1;
            coordStack.push(Coord(row+1,col));
             } 
            if (maze[row][col+1] == '.'&&(dist[row][col+1]>(currval+1)))
             {
            dist[row][col+1]=currval+1;
            coordStack.push(Coord(row,col+1));
             } 
            if (maze[row][col-1] == '.'&&(dist[row][col-1]>(currval+1)))
             {
            dist[row][col-1]=dist[row][col]+1;
            coordStack.push(Coord(row,col-1));
             }
            //maze[row][col]='C';
        }
}
        int main()
        {
            char myMaze[10][10] = {
                { 'X','X','X','X','X','X','X','X','X','X'},
                { 'X','.','.','.','.','.','X','.','.','X'},
                { 'X','X','.','X','X','.','.','.','.','X'},
                { 'X','.','.','X','.','.','.','X','.','X'},
                { 'X','.','.','.','X','X','.','X','X','X'},
                { 'X','X','X','.','.','.','.','X','.','X'},
                { 'X','X','.','.','.','X','.','X','.','X'},
                { 'X','X','.','X','.','X','.','X','X','X'},
                { 'X','X','.','.','.','X','.','.','.','X'},
                { 'X','X','X','X','X','X','X','X','X','X'}
            };

            int distances[10][10];
            determineDistances(myMaze, 6, 3, distances);
            for (int r = 0; r < 10; r++)
            {
                for (int c = 0; c < 10; c++)
                    cout << ' ' << setw(2) << distances[r][c];
                cout << endl;
            }
              // Output should be
              //  99 99 99 99 99 99 99 99 99 99
              //  99  7  6  7  8  9 99  9 10 99
              //  99 99  5 99 99  8  7  8  9 99
              //  99  5  4 99  8  7  6 99 10 99
              //  99  4  3  2 99 99  5 99 99 99
              //  99 99 99  1  2  3  4 99 99 99
              //  99 99  1  0  1 99  5 99 99 99
              //  99 99  2 99  2 99  6 99 99 99
              //  99 99  3  4  3 99  7  8  9 99
              //  99 99 99 99 99 99 99 99 99 99
            std::cin.get();

//but the output is
/*
 99 99 99 99 99 99 99 99 99 99
 99 99 99 99 99 99 99 99 99 99
 99 99 99 99 99 99 99 99 99 99
 99 99 99 99 99 99 99 99 99 99
 99 99 99 99 99 99 99 99 99 99
 99 99 99  1  2 99 99 99 99 99
 99 99  1  0  1 99 99 99 99 99
 99 99  2  1  2 99 99 99 99 99
 99 99  3  2  3 99 99 99 99 99
 99 99 99 99  6 99 99 99 99 99

*/

//Any ideas on what the error is?
        }

Output:

test row 6 col 3
test row 6 col 2
test row 7 col 2
test row 8 col 2
test row 8 col 3
test row 8 col 4
test row 9 col 4
test row 6 col 4
test row 7 col 4
test row 8 col 4
test row 7 col 4
test row 7 col 3
test row 8 col 3
 99 99 99 99 99 99 99 99 99 99
 99 99 99 99 99 99 99 99 99 99
 99 99 99 99 99 99 99 99 99 99
 99 99 99 99 99 99 99 99 99 99
 99 99 99 99 99 99 99 99 99 99
 99 99 99  1  2 99 99 99 99 99
 99 99  1  0  1 99 99 99 99 99
 99 99  2  1  2 99 99 99 99 99
 99 99  3  2  3 99 99 99 99 99
 99 99 99 99  6 99 99 99 99 99

I'm thinking that I'm probably missing a push instruction somewhere. Any ideas would be much appreciated.


In this part:

if ((maze[row-1][col] == '.')&&(dist[row-1][col]>(currval+1)))
{
    dist[row-1][col]=currval+1;
    coordStack.push(Coord(row+1,col));
} 

The last line should say row-1 instead of row+1.

0

精彩评论

暂无评论...
验证码 换一张
取 消