HDU2312 Cliff Climbing

首先附上通道：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;
}