在二维数组中显示完成的最短路径

Question

您好，我的迷宫求解器需要帮助。我有可以搜索迷宫并找到终点的代码，但现在我只需要显示最短路径。问题是，我的代码显示了我的算法所做的每一步。我可以请求提示如何只显示我需要的路径吗？

class GFG
{
    static int ROW = 9;
    static int COL = 10;
    static int[,] Maze;


    public class Point
    {
        public int x;
        public int y;

        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    };

    public class QueueNode
    {
        public Point pt;

        public int dist;

        public QueueNode(Point pt, int dist)
        {
            this.pt = pt;
            this.dist = dist;
        }
    };


    static bool IsValid(int row, int col)
    {
        return (row >= 0) && (row < ROW) &&
               (col >= 0) && (col < COL);
    }




    static int PathFind(Point start, Point end, int[,] mat)
    {

        if (mat[start.x, start.y] != 1 ||
            mat[end.x, end.y] != 1)
            return -1;


        Stack<QueueNode> stack = new Stack<QueueNode>();
        bool[,] visited = new bool[mat.GetLength(0), mat.GetLength(1)];


        stack.Push(new QueueNode(start, 0));

        int c;

        while (stack.Count > 0)
        {
            QueueNode node = stack.Pop();
            int x = node.pt.x;
            int y = node.pt.y;
            c = node.dist;
            if (x == end.x && y == end.y)
            {
                Maze[x, y] = 3;
                return c;
            }



            if (IsValid(x, y) && mat[x, y] == 1 && !visited[x, y])
            {
                stack.Push(new QueueNode(new Point(x + 1, y), c + 1));
                stack.Push(new QueueNode(new Point(x - 1, y), c + 1));
                stack.Push(new QueueNode(new Point(x, y + 1), c + 1));
                stack.Push(new QueueNode(new Point(x, y - 1), c + 1));
                Maze[x, y] = 3;


                visited[x, y] = true;
            }

        }

        return -1;

    }

    public static void Main(String[] args)
    {
        int[,] mat =    {{
                          1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                        { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                        { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                        { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                        { 1, 1, 1, 0, 1, 1, 1, 1, 1, 0 },
                        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                        { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};

        
        Maze = new int[mat.GetLength(0), mat.GetLength(1)];

        Point source = new Point(0, 0);
        Point dest = new Point(8, 9);

        int dist = PathFind(source, dest, mat);


        for (int i = 0; i < Maze.GetLength(0); ++i)
        {
            for (int j = 0; j < Maze.GetLength(1); ++j)
            {
                Console.Write(Maze[i, j]);
            }
            Console.Write("\n");
        }
        if (dist != -1)
            Console.WriteLine("Shortest Path is " + dist);
        else
            Console.WriteLine("Shortest Path doesn't exist");
    }}

我有一个原始字段，我通过算法，另一个我存储我已经通过的坐标，所以它会被标记。但我只需要标记最短路径而不是所有步骤。

例如这段代码显示：

我只需要展示这些：

Answer 1

//Maze[x, y] = 3;
Maze[x, y] = node.dist+1;

从endPoint到startPoint，每个单元格都会有成本。

最短路径可以通过为您当前所在的每个单元格找到具有最小值的邻居来找到。

在二维数组中显示完成的最短路径

Display shortest path to finish in 2D array

c#

maze