通过回溯在迷宫中寻找路径

Finding a path in a maze via backtracking

我想编写一个程序,通过回溯查找迷宫中是否存在从右上角到左下角的路径。输入数字是 n 和 m,它们是矩形迷宫和迷宫的维度,字符 '.'表示您可以通过的方块,字符 'x' 表示您无法通过的方块。我写了代码,它相当简单,但没有显示任何东西,而它应该显示“da”(塞尔维亚语“是”)和“ne”(塞尔维亚语“否”)。

#include <bits/stdc++.h>

using namespace std;

bool maze[20][20]; //defined maze of maximum size 20x20

//checking if a position is viable for moving through
bool Safe(int n, int m, int x, int y)
{
    if(x >= 0 && x < n && y >= 0 && y < m)
    {
        if(maze[x][y] == 1) return true;
    }
    return false;
}

bool Utility(int n, int m, int x, int y) //main utility function
{
    if(x == n - 1 && y == m - 1 && maze[x][y] == 1) // base case, end of maze
    {
        return true;
    }

    if(Safe(n, m, x, y))
    {
        if(Safe(n, m, x + 1, y)) // checking if it is viable to move down
        {
            if(Utility(n, m, x + 1, y))
            {
                return true;
            }
        }
        if(Safe(n, m, x, y + 1))
        {
            if(Utility(n, m, x, y + 1)) // checking if it is viable to move right
            {
                return true;
            }
        }
        if(Safe(n, m, x - 1, y))
        {
            if(Utility(n, m, x - 1, y)) // checking if it is viable to move up
            {
                return true;
            }
        }
        if(Safe(n, m, x, y - 1))
        {
            if(Utility(n, m, x, y - 1)) // checking if it is viable to move left
            {
                return true;
            }
        }
    }

    return false; // returning false
}

int main()
{
    int n, m;

    cin >> n >> m; // input dimensions of the maze

    for(int i = 0; i < n; i++) // input maze
    {
        for(int j = 0; j < m; j++)
        {
            char c;
            cin >> c;
            if(c == '.') //character '.' means a tile which you can go through
            {
                maze[i][j] = 1;
            }
            else         //character 'x' means a tile which you cannot go through
            {
                maze[i][j] = 0;
            }
        }
    }

    if(Utility(n, m, 0, 0)) //printing yes or no
    {
        cout << "da";
    }
    else
    {
        cout << "ne";
    }
    

    return 0;
}

示例输入:

8 8 
.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..

示例输出:da

问题是,如果您从 (0, 0) -> (1, 0) 出发,那么在 (1, 0) 您可以再次回到 (0, 0),这将永远循环。为避免这种情况,我创建了一个 visited 数组,如果单元格 (x, y) 已被访问,该数组的值为 true,否则为 false.

我已经用 ///////////// change here ///////////// 评论标记了我所做的更改

#include <bits/stdc++.h>

using namespace std;

bool maze[20][20]; //defined maze of maximum size 20x20
///////////// change here /////////////
bool visited[20][20];

bool Safe(int n, int m, int x, int y) //checking if a position is viable for moving through
{
    if(x >= 0 && x < n && y >= 0 && y < m)
    {
        if(maze[x][y] == 1) return true;
    }
    return false;
}

bool Utility(int n, int m, int x, int y) //main utility function
{
    if(x == n - 1 && y == m - 1 && maze[x][y] == 1) // base case, end of maze
    {
        return true;
    }

    ///////////// change here ///////////// 
    if(!visited[x][y] && Safe(n, m, x, y))
    {
        ///////////// change here /////////////
        visited[x][y] = true;

        if(Safe(n, m, x + 1, y)) // checking if it is viable to move down
        {
            if(Utility(n, m, x + 1, y))
            {
                return true;
            }
        }
        if(Safe(n, m, x, y + 1))
        {
            if(Utility(n, m, x, y + 1)) // checking if it is viable to move right
            {
                return true;
            }
        }
        if(Safe(n, m, x - 1, y))
        {
            if(Utility(n, m, x - 1, y)) // checking if it is viable to move up
            {
                return true;
            }
        }
        if(Safe(n, m, x, y - 1))
        {
            if(Utility(n, m, x, y - 1)) // checking if it is viable to move left
            {
                return true;
            }
        }
    }

    return false; // returning false
}

int main()
{
    int n, m;

    cin >> n >> m; // input dimensions of the maze

    for(int i = 0; i < n; i++) // input maze
    {
        for(int j = 0; j < m; j++)
        {
            char c;
            cin >> c;
            if(c == '.') //character '.' means a tile which you can go through
            {
                maze[i][j] = true;
            }
            else         //character 'x' means a tile which you cannot go through
            {
                maze[i][j] = false;
            }
            ///////////// change here /////////////
            visited[i][j] = false;
        }
    }

    if(Utility(n, m, 0, 0)) //printing yes or no
    {
        cout << "da";
    }
    else
    {
        cout << "ne";
    }
    

    return 0;
}

这是我测试的link:https://ideone.com/vVqAjF