求最小转弯路径(Minimizing Turns)|树

这个问题来自这里:

Paste_Image.png

上图中两个点之间存在多个路径，请求出转弯最小的路径。

思路1：
突然联想到爬楼梯的问题，用动态规划加递归，有点像图的DFS和树的前序遍历。不过这里只是输出了最短的转弯数，并没有输出路径，要输出路径的另外一个方法，找到从A到B的所有路径带转弯数（这个算法在王道书籍P203），然后进行排序，算法复杂度为O（V+E）+O（所有路径之和进行排序）

int GetMinTurnPath(Start,Dest,Buff,len)
{
    if(Start==NULL)
        return

    //递归结束条件
    if(Start==Dest)
        return 0;

    //直走直到遇到有转弯，转弯可能一个向前，一个转弯
    Move forward until across with turn

    //
    Path1 = 1 + GetMinTurnPath(ForWard,Dest)
    Path2 = GetMinTurnPath(Turn,Dest);

    return max(Path1,Path2)
}