首先附上通道：hdu2312
HDU2312，这题是我去年寒假做的题，前不久又看到了去年写的解题报告，感觉还是很有意思
题意
- 给出一个悬崖，给出若干个起点和终点，问从某起点到某终点的最短距离是多少，若不能到达则输出 -1，规则为左脚跨出之后必须跨右脚，且每跨一脚都有一定的范围限制。
- 一开始我想到的是用广度优先搜索，从每个S出发，扩展开去，每到一个点，就继续扩展，直到扩展完所有的点，但是出现了两个问题就是，左脚和右脚的交替，还有就是，这样不断扩展，会导致队列不断增大，最终会永远运行下去而不能结束。
解题思路
好像先是网上搜了一波，搜到了这些spfa、暴力pfs
但代码貌似都有点高深……弄了好久，最后弄出的spfa+优先队列的方法，没用什么C++的库，就是结构体+数组。。不过，过了一年再来看代码，也不是很好理解（尴尬）
大致的解析
- 下面代码中temp表示的是优先队列的长度，q表示的是优先队列，dp表示的是图中每个点的最小到达距离，book用来去掉重复的节点。
- 一开始，把所有的起点入队，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队列中，在下次递归中继续用它。这个思想和Dijkstra算法类似，不断刷新最小值，并以这个最小值重新作为一个新的起点。
- 这里还有一个突破点就是3维数组表示左右脚。二维数组来模拟脚步的移动并不难，而三维数组其实就是1+1=2。nextstep[2][9][2]由两部分组成nextstep[0]和nextstep[1]，分别代表的左右脚移动的二维数组，其实就是把两个数组合在一起，方便写代码，如果由两个二维数组来代替，不仅仅是脚步处理的问题，优先队列也需要相应的变化，难度就大了，所以三维数组还是不可缺少的。
代码
#include <iostream>
#define N 61*31
using namespace std;
struct que{
int x;
int y;
}q[N*5],endT[N]; //q表示的是优先队列，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表示优先队列的游标,dp对应优先队列的值，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){
//终止条件为优先队列为空，此处的队列因为加上了刷新最小值的限制，所以队列增长的数量有限
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的核心，也就是优先队列，如果达到可以刷新最下值，就刷新，如果刷新
//之后此结点已在队列中则不再重复入队
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;
}
