用C++改的最短路径算法

Question

using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication2
{
    public struct Postion
    {
        public int X;
        public int Y;
        public Postion(int X, int Y)
        {            this.X = X;
            this.Y = Y;
        }    };
    class Program
    {
        static int[,] maze = new int[10, 10] {{ 0, 0, 0, 0,-1, 0, 0, 0, 0, 0},
{ 0,-1,-1, 0, 0, 0, 0,-1, 0, 0},
{ 0, 0,-1, 0,-1, 0, 0,-1, 0,-1},
{ 0, 0,-1, 0,-1, 0, 0,-1, 0,-1},
{ 0, 0, 0, 0,-1,-1, 0,-1, 0, 0},
{ 0, 0,-1, 0, 0, 0, 0, 0, 0, 0},
{ 0,-1, 0, 0,-1, 0,-1,-1, 0, 0},
{ 0, 0, 0,-1, 0, 0, 0,-1, 0,-1},
{-1, 0, 0,-1, 0, 0, 0,-1, 0,-1},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0,-1}
};  static void  printPath(Stack<Postion> path)//打印路径没用的
        {
                /*  while (!path.empty())
            {
                printf("[%d][%d] ==>> [%2d]\n",
                    path.top().X, path.top().Y, 
                    maze[path.top().X][path.top().Y]-1);
                path.pop();
            }*/
            System.Console.Write(path.Count);
        }      /*  static void printMat(int mat[10,10])//打印地图没用的 
        {
            for (int i = 0; i < 10 ; i++)
            {
                for (int j = 0; j < 10 ; j++)
                {
                    printf("%2d ", mat[i][j]);
                }                printf("\n");
            }
        }
        */
           
        //开始用用的
       static  bool isCanGo(int prePosValue,
                      int posX,
                      int posY)
        {
            if (posX < 0 || posX > 9 // 越界
                || posY < 0 || posY > 9
                || maze[posX, posY] == -1) // 墙
            {
                return false;
            }            if (maze[posX, posY] == 0) // 未走过
                return true;
            else // 更近的路径
                return (prePosValue + 1) < maze[posX, posY];
        }
        static Stack<Postion> stackpath = new Stack<Postion>(); // 路径        static Postion[] offset = new Postion[4];  // 偏移量           static void shortestPath(Stack<Postion> path,
                           Postion start,
                           Postion end)
{
if (   start.X == end.X 
&& start.Y == end.Y)
{
if (path.Count< stackpath.Count || stackpath.Count == 0) // 更短的路径
stackpath = path;
return;
}

for (int i = 0; i < 4; i++)
{
int nNextPosX = start.X + offset[i].X;
int nNextPosY = start.Y + offset[i].Y; if (isCanGo(maze[start.X,start.Y], nNextPosX, nNextPosY))
{
maze[nNextPosX,nNextPosY] = maze[start.X,start.Y] + 1;            path.Push(new Postion(nNextPosX, nNextPosY)); shortestPath(path, new Postion(nNextPosX, nNextPosY), end); path.Pop();
}
}
}
   
      static void Main(string[] args)
        {            offset[0].X = -1; offset[0].Y = 0; // 上
            offset[1].X = 1; offset[1].Y = 0; // 下
            offset[2].X = 0; offset[2].Y = -1; // 左
            offset[3].X = 0; offset[3].Y = 1; // 右
            Postion start = new Postion(2, 1);
            Postion end = new Postion(6, 8);
            maze[start.X, start.Y] = 1; // 置起点值1, 防止走回起点
            shortestPath(new Stack<Postion>(), start, end);
          /*  while (!stackpath.empty())
            {
                System.Console.Write(stackpath.Peek()).X; stackpath.Peek().Y;
                    maze[stackpath.Peek().X; stackpath.Peek().Y] - 1);
        
                stackpath.Pop();
            }*/
            printPath(stackpath);
           
            System.Console.Write("xiaoxin");        }
    }
}不知道为什么stackpath 总为空，对C# 一点都不会，可是要用到最短路径的算法。用C++的算法改了一个但是不明白这个问题是怎么产生的！！希望给我给答案，方便给个弄好的代码也行。先谢谢啦

Answer 1

http://www.dearbook.com.cn/WebResource.aspx?id=466

Answer 2

其实就差一点点就对了!
你把
if (path.Count< stackpath.Count || stackpath.Count == 0)    // 更短的路径
    stackpath = path;
return;
换成if (path.Count< stackpath.Count || stackpath.Count == 0)    // 更短的路径
    stackpath = new Stack<Postion>(path);
return;就可以了。原因呢，你在找到答案时这样赋值：stackpath = path; 他们都是引用类型，stackpath和path指向同一个数据栈。
随后呢，path.Pop();不断的把数据栈的内容弹出。最终stackpath指向了一个空栈。解决方法就是新建一个path的拷贝，new Stack<Postion>(path)，你的问题就解决了。题外话，你可以考虑用A*算法来做。由于A*带有启发约束，能更快的找到答案。