首先附上通道：hdu2312

HDU2312，這題是我去年寒假做的題，前不久又看到了去年寫的解題報告，感覺還是很有意思

題意

• 給出一個懸崖，給出若干個起點和終點，問從某起點到某終點的最短距離是多少，若不能到達則輸出 -1，規(guī)則為左腳跨出之后必須跨右腳，且每跨一腳都有一定的范圍限制。
• 一開始我想到的是用廣度優(yōu)先搜索，從每個S出發(fā)，擴展開去，每到一個點，就繼續(xù)擴展，直到擴展完所有的點，但是出現了兩個問題就是，左腳和右腳的交替，還有就是，這樣不斷擴展，會導致隊列不斷增大，最終會永遠運行下去而不能結束。

解題思路

好像先是網上搜了一波，搜到了這些spfa、暴力pfs
但代碼貌似都有點高深……弄了好久，最后弄出的spfa+優(yōu)先隊列的方法，沒用什么C++的庫，就是結構體+數組。。不過，過了一年再來看代碼，也不是很好理解（尷尬）

大致的解析

• 下面代碼中temp表示的是優(yōu)先隊列的長度，q表示的是優(yōu)先隊列，dp表示的是圖中每個點的最小到達距離，book用來去掉重復的節(jié)點。
• 一開始，把所有的起點入隊，dp相應的值設置成0。然后，每次遞歸，都從頭開始遍歷q隊列。里面的每個點都左右腳各處理一遍。for(k=0;k<2;k++)處理左右腳，for(i=0;i<9;i++)然后分別遍歷左右腳能到達的地方。
• 這樣會出現一種情形，就是這個點可以從A點跨左腳到達，也可以從B點跨右腳到達，然后就出現了spfa的關鍵一步

if(dp[k][px][py]>dp[1-k][tx][ty]+v){
    dp[k][px][py]=dp[1-k][tx][ty]+v;
    if(!book[k][px][py]){
           book[k][px][py]=1;  
           q[temp].x=px;q[temp++].y=py;   
    }
}

從上面的代碼中不難看出，某一個點在dp隊列中的值，取決于能夠 達到這個點的最小距離，并且把這個點納入到q隊列中，在下次遞歸中繼續(xù)用它。這個思想和Dijkstra算法類似，不斷刷新最小值，并以這個最小值重新作為一個新的起點。

• 這里還有一個突破點就是3維數組表示左右腳。二維數組來模擬腳步的移動并不難，而三維數組其實就是1+1=2。nextstep[2][9][2]由兩部分組成nextstep[0]和nextstep[1]，分別代表的左右腳移動的二維數組，其實就是把兩個數組合在一起，方便寫代碼，如果由兩個二維數組來代替，不僅僅是腳步處理的問題，優(yōu)先隊列也需要相應的變化，難度就大了，所以三維數組還是不可缺少的。

代碼

#include <iostream>
#define N 61*31
using namespace std;
struct que{
    int x;
    int y;
}q[N*5],endT[N];  //q表示的是優(yōu)先隊列，endT存儲的是終點位置
//nextstep用來模擬左右腳的移動
int nextstep[2][9][2]={ {{-2,-1},{-1,-1},{-1,-2},{0,-1},{0,-2},{0,-3},{1,-1},{1,-2},{2,-1}},{{-2,1}, {-1,1}, {-1,2}, {0,1}, {0,2}, {0,3}, {1,1}, {1,2}, {2,1}}}; 
int w,h,temp,dp[2][61][31],book[2][61][31],inf=999999;
//temp表示優(yōu)先隊列的游標,dp對應優(yōu)先隊列的值，book去掉重復的結點
char map[61][31];
int min(int a,int b){
    return a<b?a:b;
}
void bfs(){
    int head=0,tx,ty,i,k,px,py,v;
    while(head<temp){
        //終止條件為優(yōu)先隊列為空，此處的隊列因為加上了刷新最小值的限制，所以隊列增長的數量有限
        tx=q[head].x;ty=q[head++].y;   //取得隊列最前端對應的坐標
        for(k=0;k<2;k++){
            if(book[1-k][tx][ty]==1){   //判斷對應的左右腳是否已入列
                book[1-k][tx][ty]=0;   //取消入列標記
                for(i=0;i<9;i++){
                    px=tx+nextstep[k][i][0];  //分別移動所有限制以內的地方
                    py=ty+nextstep[k][i][1];
                    if(px>=0&&px<h&&py>=0&&py<w&&map[px][py]!='X'){
                        if(map[px][py]=='S'||map[px][py]=='T') v=0;  //起點和終點對應的值為0
                        else v=map[px][py]-48;
                        if(dp[k][px][py]>dp[1-k][tx][ty]+v){
                            //spfa的核心，也就是優(yōu)先隊列，如果達到可以刷新最下值，就刷新，如果刷新
                            //之后此結點已在隊列中則不再重復入隊
                            dp[k][px][py]=dp[1-k][tx][ty]+v;
                            if(!book[k][px][py]){
                                book[k][px][py]=1;   //若未入隊，則標記入隊
                                q[temp].x=px;q[temp++].y=py;   //并擴大隊列
                            }
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    int i,j,t,cot;
    while(cin>>w>>h&&w,h){
        temp=0;
        t=0;
        for(i=0;i<h;i++)
            for(j=0;j<w;j++){
                dp[0][i][j]=dp[1][i][j]=inf;   //將左右腳對應的整幅圖對應的值初始化為Inf
                book[0][i][j]=book[1][i][j]=0;   //初始化在隊列中的結點
                scanf(" %c",&map[i][j]);
                if(map[i][j]=='S'){
                    q[temp].x=i;   //將開始的起點坐標先入列，從起點擴展開去的結點后面也依次入列
                    q[temp++].y=j; 
                    dp[0][i][j]=dp[1][i][j]=0;  //起點對應的值為0
                    book[0][i][j]=book[1][i][j]=1;  //標記已入列
                }
                if(map[i][j]=='T'){   //加入結束隊列
                    endT[t].x=i;
                    endT[t++].y=j;                  
                }
            }
        bfs();
        cot=inf;    
        for(i=0;i<t;i++)  //比較每個終點的左右腳的值大小
            cot=min(cot,min(dp[0][endT[i].x][endT[i].y],dp[1][endT[i].x][endT[i].y]));
        if(cot==inf) cout<<"-1"<<endl;
        else cout<<cot<<endl;
    } 
    return 0;
}