迷宫遍历打印每条可能的路径 C++

Question

这是我关于堆栈溢出的第一个问题，这是我的作业。我要做的就是找到从头到尾所有可能的路径。我正在做的是，如果找到 '-' 并且函数的参数是 '-' 所在的索引，我将调用该函数。当前参数被压入堆栈。在进一步解释之前，我想展示输出和迷宫。

迷宫

5 6
s - - - - -
- * * * * -
- * * * * - 
- * * * * -
- - - - - e

开始的两个 int 是行和列。

输出

00,01,11,21,22,02,03,13,23,22,04,05,15,25,35,45,44,43,42,32,22

从栈中取出输出。

在某种程度上，输出是正确的，因为您可以看到该函数正在遍历每条路径。我无法做的是跟踪功能以及我为什么要这样做？因为我想从头开始打印所有路径（在本例中为 0、0）。当函数有两条路径要遍历时，如何跟踪函数以便我可以从起始索引打印它？

预期输出

00,01,11,21,22
00,01,02,03,13,23,22
00,01,02,03,04,05,15,25,35,45,44,43,42,32,22

如有必要，我也会提供代码。我有编辑代码。我正在将索引 (1,0) 推入堆栈，例如先 0 然后 1，然后弹出两个以将其删除。我理解为什么我的输出是这样的（如上所述），因为，以 (0,0) 处程序中的迷宫为例，它有向上或向下两个选项。它下降了，因为所有这些语句都是 if not if else 程序在函数执行后检查其他条件，所以它转到另一个正确的选项。好的，那么输出呢？所有索引都被压入堆栈，当找到 'e' 时，它会打印所有存储的索引，但不会删除它们。对于这个例子，我可以在打印后从堆栈中弹出所有内容，输出会很好（不重复）再举个例子

例子

6 6 小号 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 e

在此示例中，您可以看到它在 (0,2) 处有两个选项，因此我无法在到达第一个路径末端后从此处弹出堆栈中的所有内容。因为它也会弹出 (0,0) 和 (0,1)。我想要的是只弹出到 (0,2)

这就是我想要做的。

#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
ofstream fout("Q1(output).txt");
ifstream fin("Q1.txt");
class stack
{
    private:
        int row,col;
        int top;
        string str;
        int sourceA,sourceB,destinationA,destinationB;
        char **store;//arr which has maze is passed into class . 'store' has maze.
    public: 
            stack(int row,int col)//constructor , paramerters are rows and cols
        {
            
            this->row=row;
            this->col=col;
            top=-1;
            sourceA=0;
            sourceB=0;
        }   
    void finish()
    {
        while(top!=-1)
        {
            top--;
        }
    }
    
    void push(int dataA,int dataB )//push two indexes in str like (0,1) pushed as first 0 then 1 
    {
        if(top==-1)
        {
        top++;
        str[top]=dataA ;
        top++;
        str[top]=dataB  ;
        }
        else
        {
        top++;
        str[top]='1';
        top++;
        str[top]=dataA ;
        top++;
        str[top]=dataB  ;
                
        }
        
    }
    void  pop(int varA ,int varB)//This function was made for other purpose but not used 
    {
        for(int a=0;a<top+1;a++)
        {
            if(a==varA && a+1==varB )
            {
                top=a-2;
                cout<<top;
            }
        }
        
        cout<<endl;
    }
    int ret()
    {
        return top;
    }
    void empty()
    {
        if(top==-1)
        cout<<"\nEmpty\n";
        else 
        cout<<"\nNot Empty\n";
    }
    void get(char **arr)// saving arr(Maze) into store
    {
            char ch;
            store=NULL;
            store=new char*[row];
            for(int a=0;a<row;a++)
            {
                store[a]=new char[col];
                for(int b=0;b<col;b++)
                {
                    
                store[a][b]=arr[a][b];  
                cout<<store[a][b];
                            
                if(arr[a][b]=='s')
                {
                    sourceA=a;//saving the 's' index , my inititate starts from here .
                    sourceB=b;
                        
                }
                else if(arr[a][b]=='e')
                {
                    destinationA=a;//saving the 'e' index , used later.
                    destinationB=b; 
                }
                }
                cout<<endl;         
            }
            }
            int getA()
            {
                return sourceA;
            }
            int getB()
            {
                return sourceB;
            }
            int getAD()
            {
                return destinationA;
            }
            int getBD()
            {
                return destinationB;
            }
            
            int initiate(int a,int b)
            {
                 int tempA,tempB;
                push(a,b);
                
                 if(a>0 )
                {
                
                 if(store[a-1][b]=='1'&&store[a-1][b]!='v')
                {
                    
                    store[a][b]='v';
                    initiate(a-1,b);
                    store[a][b]='1' ;
                    
                }
                }
                
                 if(b>0 )
                {
                
                 if(store[a][b-1]=='1'&&store[a][b-1]!='v')
                {
                    
                    store[a][b]='v';
                    initiate(a,b-1);
                    store[a][b]='1' ;
                
                    
                }
                }
                
                if(a!=row-1)
                {
                
                 if(store[a+1][b]=='1'&&store[a+1][b]!='v')
                {
                    
                    store[a][b]='v';
                    initiate(a+1,b);
                    store[a][b]='1' ;
            
                }
                }
                
                if(b!=col-1)
                {
        
                 if(store[a][b+1]=='1'&&store[a][b+1]!='v')
                {
                    
                    store[a][b]='v';                
                    initiate(a,b+1);
                    store[a][b]='1' ;
                
                }
                }
                 if(a+1==destinationA && b==destinationB ||a-1==destinationA && b==destinationB ||a==destinationA && b+1==destinationB ||a==destinationA && b-1==destinationB )
                {
                    push(destinationA,destinationB);                
                    cout<<"\nPath  : \n";
                    print1();
                                
                        
                }
            pop();
            
            }
            void print1()
            {
                for(int  a=0;a<top+1;a++)
                {
                    
                    if(str[a]!='1')
                    {
                    int ret=str[a];
                    cout<<ret;
                    fout<<ret;
                    }
                    else
                    {
                        cout<<endl;
                        fout<<endl;                             
                    }
                }
                
                fout.close();
                }
    int pop()
    {
        
        int ret=str[top];
        top--;
        int ret1=str[top];
        top--;
    
    }   
        void show()
        {
            cout<<endl<<endl;
            for(int a=0;a<row;a++)
                {
            for(int b=0;b<col;b++)
                {
                    cout<<store[a][b];
                    
                }
                cout<<endl;
        }
        }
        
};
main()
{
    
    char ch;
    int row,col;
    fin >> row;
    fin >> col;
    stack s(row,col);
    char **arr=NULL;
    arr=new char*[row];     
            for(int a=0;a<row;a++)
            {
            arr[a]=new char[col];       
            for(int b=0;b<col;b++)
                {
                fin>>ch;
                arr[a][b]=ch;           
                }
                 
            }

    fin.close();
    s.get(arr);
    s.initiate(s.getA(),s.getB());
    
    s.show();
    
    exit(1);
    }

Answer 1

打印所有路径可以像您一样使用递归来完成，但是您需要跟踪您为达到目标所走的路径，并在每次到达目的地时打印它或保存它在一个容器中。我更喜欢后一种方法。该路径可以是堆栈或其他支持 push/pop 操作的结构。您在遍历中访问的每个节点都应添加到路径中，并在其所有邻居都已完全展开后弹出。

这是伪代码中的递归路径构建算法：

function DFS(row: int, col: int, maze: char[][], path: int[][], result: int[][][]) {
    path.push([row, col])

    if ([row, col] is the destination) {
        result.add(path)
    }
    else {
        for (direction in each_cardinal_direction) {
            new_row = row + direction.row
            new_col = col + direction.col

            if (in_bounds(new_row) and in_bounds(new_col) and 
                maze[new_row][new_col] is unvisited) {

                maze[row][col] = visited
                DFS(new_row, new_col, maze, path, result)
                maze[row][col] = unvisited
            }
        }
    }

    path.pop()
}

我不是很清楚你为什么同时使用显式和隐式状态；通常，当运行和 DFS 时，使用显式堆栈和 while 循环或使用递归并将所有状态存储为调用堆栈上的帧。考虑改进命名清晰度、设计和 spacing/indentation，以便您的逻辑更容易理解。

例如，str 是一个充当堆栈的数组，应该这样命名，而您的 stack class 实际上根本不是堆栈，而是而是一个迷宫求解器。您的 pop 函数不准确，一次只能删除一个元素。

此外，由于您使用的是 C++ classes 和字符串，您也可以利用容器。

这是一个临时修改迷宫的递归示例，添加墙壁以标记访问过的节点以避免循环：

#include <iostream>
#include <vector>

void DFS(
    int row, int col,
    std::vector<std::vector<char>> &maze, 
    std::vector<std::pair<int, int>> &path,
    std::vector<std::vector<std::pair<int, int>>> &result
) {
    path.push_back(std::make_pair(row, col));

    if (maze[row][col] == 'e') {
        result.push_back(path);
    }
    else {
        int dirs[][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

        for (auto d : dirs) {
            int r = d[0] + row;
            int c = d[1] + col;

            if (r >= 0 && c >= 0 && r < maze.size() && 
                c < maze[r].size() && maze[r][c] != '*') {
                maze[row][col] = '*';
                DFS(r, c, maze, path, result);
                maze[row][col] = '-';
            }
        }
    }

    path.pop_back();
}

std::vector<std::vector<std::pair<int, int>>> 
getPaths(std::vector<std::vector<char>> maze) {
    std::vector<std::vector<std::pair<int, int>>> result;
    std::vector<std::pair<int, int>> path;
    int row = -1;
    int col = -1;

    for (int i = 0; i < maze.size() && row == -1; i++) {
        for (int j = 0; j < maze[i].size() && col == -1; j++) {
            if (maze[i][j] == 's') {
                row = i;
                col = j;
            }
        }
    }

    DFS(row, col, maze, path, result);
    return result;
}

int main() {
    std::string raw = "s-----\n*-*-*-\n*-e-*-\n**-**-\n**----";
    std::vector<std::vector<char>> maze;
    std::vector<char> row;

    for (int i = 0; i < raw.size(); i++) {
        if (raw[i] == '\n') {
            maze.push_back(row);
            row.clear();
        }
        else {
            row.push_back(raw[i]);
        }
    }

    maze.push_back(row);

    for (auto &path : getPaths(maze)) {
        std::cout << std::endl << '[';

        for (auto &cell : path) {
            std::cout << '(' << cell.first << 
                      "," << cell.second << ')';
        }

        std::cout << ']' << std::endl;
    }
}

输出：

[(0,0)(0,1)(0,2)(0,3)(0,4)(0,5)(1,5)(2,5)(3,5)(4,5)(4,4)(4,3)(4,2)(3,2)(2,2)]
[(0,0)(0,1)(0,2)(0,3)(1,3)(2,3)(2,2)]
[(0,0)(0,1)(1,1)(2,1)(2,2)]

Try it!

迷宫遍历打印每条可能的路径 C++

Maze Traversal prints every possible path C++

c++

stack

maze

迷宫

输出

预期输出

例子