迷宫：寻找从起点到终点的最短路径

Question

我目前正在学习一些CS基础知识（从一周前开始），我偶然发现了这一挑战。迷宫是列表的列表，其中'#'表示墙壁，' '表示开放路径。根据连续坐标(col, row)，我应该找到从左下角到右上角的最短路径。我必须做一个不导入任何东西的函数。

例如：

maze = 
       [[' ', '#', ' ', '#', ' '],
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', '#', ' ', '#', ' '], 
        [' ', ' ', ' ', ' ', ' '], 
        ['#', ' ', '#', ' ', ' '], 
        [' ', ' ', '#', '#', '#']]

首先，我获得起点坐标(0, 9)和终点坐标(4, 0)。然后，我需要找到最短的路径。预期结果将是：[(0, 9), (1, 9), (1, 8), (1, 7), (2, 7), (3, 7), (4, 7), (4, 6), (4, 5), (4, 4), (4, 3), (4, 2), (4, 1), (4, 0)]。

这是我的代码：

def grid(maze):
    ''' Maze Properties'''
    num_rows = len(maze)
    num_cols = len(maze[0])
    end_pt = (num_cols - 1, 0)
    start_pt = (0, num_rows - 1)
    print(start_pt, end_pt)

    '''Recursive Function'''

    def find_shortest(maze, start_point, end_point, visited, shortest_path):
        '''BASE CASE'''
        if start_point == end_point:
            return shortest_path


        adj_points = []
        '''FIND ADJACENT POINTS'''
        current_row = start_point[1]
        current_col = start_point[0]

        #UP
        if current_row > 0:
            if maze[current_row - 1][current_col] == " ":
                adj_points.append((current_col, current_row - 1))

        #RIGHT
        if current_col < (len(maze[0])-1):
            if maze[current_row][current_col] == " ":
                adj_points.append((current_col + 1, current_row))
        #DOWN
        if current_row < (len(maze) - 1):
            if maze[current_row + 1][current_col] == " ":
                adj_points.append((current_col, current_row + 1))
        #LEFT
        if current_col > 0:
            if maze[current_row][current_col - 1] == " ":
                adj_points.append((current_col - 1, current_row))

        print(adj_points)
        if all(elem in visited for elem in adj_points):
            return

        '''LOOP THROUGH ADJACENT PTS'''
        for point in adj_points:
            if point not in visited:
                visited.append(point)
                shortest_path.append(point)
                return find_shortest(maze, point, end_point, visited, shortest_path)



    path = [start_pt]
    visited = [start_pt]
    shortest_path = find_shortest(maze, start_pt, end_pt, visited, path)
    return shortest_path

我相信问题是，如果我走到了尽头，它应该回溯到可以选择的最后一点，我没有弄清楚该怎么做。

NOTE：我相信这是DFS，但也应感谢BFS解决方案。

Answer 1

修改此处给出的帖子：https://www.techiedelight.com/find-shortest-path-in-maze/

#include <iostream>
#include <vector>
#include <climits>
#include <cstring>
using namespace std;

// M x N matrix
#define M 10
#define N 10

// Check if it is possible to go to (x, y) from current position. The 
// function returns false if the cell has value 0 or already visited
bool isSafe(int mat[M][N], int visited[M][N], int x, int y)
{
    if (mat[x][y] == 0 || visited[x][y])
        return false;

    return true;
}

// if not a valid position, return false
bool isValid(int x, int y)
{
    if (x < M && y < N && x >= 0 && y >= 0)
        return true;

    return false;
}

// Find Shortest Possible Route in a Matrix mat from source cell (0, 0) 
// to destination cell (x, y)
// min_dist is passed by reference and stores length of longest path 
// from source to destination found so far dist maintains length of 
// path from source cell to current cell (i, j)
void findShortestPath(int mat[M][N], int visited[M][N], int i, int j,
                int x, int y, int& min_dist, int dist, vector<pair<int,int>> &shortestPath, vector<pair<int,int>> &currentPath)
{
    // if destination is found, update min_dist
    if (i == x && j == y) 
    {
        if(dist<min_dist){ // If a shorter distance is found
            min_dist = dist; // Update distance
            shortestPath = currentPath; // Update path
            shortestPath.push_back({y,x}); // Push the destination coordinates
        }
        return;
    }

    // set (i, j) cell as visited
    visited[i][j] = 1;
    currentPath.push_back({j,i});

    // go to bottom cell
    if (isValid(i + 1, j) && isSafe(mat, visited, i + 1, j))
        findShortestPath(mat, visited, i + 1, j, x, y, min_dist, dist + 1,shortestPath,currentPath);

    // go to right cell      
    if (isValid(i, j + 1) && isSafe(mat, visited, i, j + 1))
        findShortestPath(mat, visited, i, j + 1, x, y, min_dist, dist + 1,shortestPath,currentPath);

    // go to top cell
    if (isValid(i - 1, j) && isSafe(mat, visited, i - 1, j))
        findShortestPath(mat, visited, i - 1, j, x, y, min_dist, dist + 1,shortestPath,currentPath);

    // go to left cell
    if (isValid(i, j - 1) && isSafe(mat, visited, i, j - 1))
        findShortestPath(mat, visited, i, j - 1, x, y, min_dist, dist + 1,shortestPath,currentPath);

    // Backtrack - Remove (i, j) from visited matrix
    visited[i][j] = 0;
    currentPath.pop_back();
}

int main()
{
    int mat[M][N] = 
    {
        { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
        { 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 },
        { 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 },
        { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
        { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
        { 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 },
        { 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
        { 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
        { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
        { 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 },
    };

    // construct a matrix to keep track of visited cells
    int visited[M][N];
    vector<pair<int,int>> shortestPath, currentPath;
    // initially all cells are unvisited
    memset(visited, 0, sizeof visited);

    int min_dist = INT_MAX;
    int src_x = 0, src_y = 0, dest_x = 7, dest_y = 5;
    findShortestPath(mat, visited, 0, 0, 7, 5, min_dist, 0,shortestPath,currentPath);

    if(min_dist != INT_MAX){
        cout << "The shortest path from source to destination "
                "has length " << min_dist;
        cout<< "\nPath is ";
        cout<<"[";
        for(auto i:shortestPath)
            cout<<"("<<i.first<<","<<i.second<<")"<<" ";
        cout<<"]";
    }
    else 
        cout << "Destination can't be reached from given source";

    return 0;
}