最短路徑C＃

Question

Iam試圖做一個程序給我們在地圖上的最短路徑（地圖是一個有矩形的圖片，我的轉彎點是矩形的邊緣點，任何人都可以幫我找到最短路徑點？

正如你所看到的，我們有開始點和結束點，必須從開始到結束，路徑必須從點開始，路徑不能在矩形上，因爲它是我的牆，所以不能進入或。在它 所以任何機構可以幫助???

Answer 1

如果效率是不是一個問題，一個簡單的解決方案是好的，你可以考慮以下僞代碼：

visited = new bool[N,M] 
points = new List<Point>() 
prev = new List<int>() 
points.Add(Begin) 
prev.Add(-1) 
visited[Begin.X, Begin.Y] = true 

for(i = 0; i < points.Length; i++) 
    p = points(i) 
    foreach neighbor of p 
     if neighbor is not wall && !visited[neighbor.X, neighbor.Y] 
      points.Add(neighbor) 
      prev.Add(i) 
      visited[neighbor.X, neighbor.Y] = true 
      if neighbor == End 
       // we are done, print path (without Begin and End) 
       j = i 
       while j != 0 
        print points[j] 
        j = prev[j] 
       return 
// no solution found 

（這只是洪水的修改填補算法，http://en.wikipedia.org/wiki/Flood_fill）