递归解决一个迷宫C ++ [英] Solving a maze recursively C++

问题描述

我试图写一个函数，如果它找到一个迷宫的结尾，将返回一个值，如果没有找到结束，则返回false。迷宫表示为网格，点在右上角的0,0。网格中的每个正方形都可以采用整数值。除了迷宫的结束之外，每个正方形的值被初始化为零，其被设置为值2并且位于左下角。当程序移动通过迷宫时，它应该将当前路径上的平方值设置为1（这将允许打印输出显示程序达到目标时的路径）。这是我到目前为止。我将如何递归地找到迷宫的尽头？我想我的递归调用有问题，但我不知道如何继续。

I am trying to write a function that will return a value of true if it finds the end of a maze, and false if it does not find the end. The maze is represented as grid with point 0,0 in the upper right corner. Each square in the grid can take on an integer value. The value of each square is initialized to zero except for the "end" of the maze, which is set to a value of 2 and is located in the bottom left corner. As the program moves through the maze, it should set the values of squares on the current path to 1 (this will allow the print-out to show the path when the program reaches the goal). This is what I have so far. How would I recursively find the end of the maze? I think I have a problem with my recursive call but I'm not sure how to proceed.

bool solve(Maze &theMaze, int x, int y) {

    if (x > theMaze.getHeight() || y > theMaze.get_width() || x<0 || y<0)
        return false;

    if (theMaze.get_position(x,y) == 2)
        return true;

    theMaze.set_position(x,y,1);

    if (isWallBelow == false && theMaze.get_position(x,y+1) != 1)
        solve(theMaze, x, y+1);

    if (isWalltoRight == false && theMaze.get_position(x+1,y) != 1)
        solve(theMaze, x+1, y);

    if (isWalltoLeft == false && theMaze.get_position(x-1,y) !=1)
        solve(theMaze, x-1, y);

    if (isWallAbove == false && theMaze.get_position(x, y-1) !=1)
        solve(theMaze, x, y-1);

    return false;

}

推荐答案

不传播返回。

没有给你za代码，这是你需要做的：

Without giving you za code, this is what you need to do:

对于每个可能的方向：

• 如果递归调用返回 true 结束。所以返回 true


• 否则表示你没有找到结束。尝试下一个方向


• 如果没有方向给您 true ，则无法从此处到达结束，因此返回 false 。

• if the recursive call returns true it means you found the end. So return true
• else it means you didn't find the end through here. Try next direction
• if no direction gave you true, then it is not possible to reach the end from here so return false.

此外，您还需要：

• 将路径设置为1，并在回溯时将其重置为0


• 考虑到在圆圈中运行上一个bulet点）。

这篇关于递归解决一个迷宫C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！