题目地址：HDU 1428

先用BFS+优先队列求出全部点到机房的最短距离。然后用记忆化搜索去搜。

代码例如以下：

#include <iostream>

#include <string.h>

#include <math.h>

#include <queue>

#include <algorithm>

#include <stdlib.h>

#include <map>

#include <set>

#include <stdio.h>

using namespace std;

#define LL __int64

#define pi acos(-1.0)

const int mod=1e9+7;

const int INF=0x3f3f3f3f;

const double eqs=1e-9;

const int MAXN=50+10;

int d[MAXN][MAXN], mp[MAXN][MAXN], vis[MAXN][MAXN], n;

LL dp[MAXN][MAXN];

int jx[]={0,0,1,-1};

int jy[]={1,-1,0,0};

struct node

{

        int x, y, step;

        bool operator < (const node &tmp) const{

                return tmp.step<step;

        }

};

void bfs()

{

        node f1, f2;

        f1.x=n-1;

        f1.y=n-1;

        f1.step=mp[n-1][n-1];

        d[n-1][n-1]=mp[n-1][n-1];

        vis[n-1][n-1]=1;

        priority_queue<node>q;

        q.push(f1);

        while(!q.empty()){

                f1=q.top();

                q.pop();

                for(int i=0;i<4;i++){

                        f2.x=f1.x+jx[i];

                        f2.y=f1.y+jy[i];

                        if(f2.x>=0&&f2.x<n&&f2.y>=0&&f2.y<n&&!vis[f2.x][f2.y]){

                                vis[f2.x][f2.y]=1;

                                f2.step=f1.step+mp[f2.x][f2.y];

                                d[f2.x][f2.y]=f2.step;

                                q.push(f2);

                        }

                }

        }

}

LL dfs(int x, int y)

{

        int i, a, b;

        if(dp[x][y]) return dp[x][y];

        for(i=0;i<4;i++){

                a=x+jx[i];

                b=y+jy[i];

                if(a>=0&&a<n&&b>=0&&b<n&&d[a][b]<d[x][y]){

                        dp[x][y]+=dfs(a,b);

                }

        }

        return dp[x][y];

}

int main()

{

        int i, j;

        while(scanf("%d",&n)!=EOF){

                for(i=0;i<n;i++){

                        for(j=0;j<n;j++){

                                scanf("%d",&mp[i][j]);

                        }

                }

                memset(dp,0,sizeof(dp));

                memset(vis,0,sizeof(vis));

                bfs();

                dp[n-1][n-1]=1;

                printf("%I64d\n",dfs(0,0));

        }

        return 0;

}