HDU-1428（记忆化搜索）

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

struct node {
    int x,y;
    int d;
};
int n;
int map[57][57];
int dis[57][57];
__int64 dp[57][57];
int vis[57][57];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

bool operator < (node a,node b) {
    return a.d>b.d;
}

void dfs()
{
    priority_queue<node> que;
    memset(vis,0,sizeof(vis));
    node tmp,next;
    tmp.x = n;
    tmp.y = n;
    tmp.d = map[n][n];
    que.push(tmp);
    while(!que.empty())
    {
        tmp = que.top();
        que.pop();
        if(vis[tmp.x][tmp.y])
            continue; 
        vis[tmp.x][tmp.y] = 1;
        dis[tmp.x][tmp.y] = tmp.d; 
        for(int i = 0;i < 4;i++) {
            next.x = tmp.x+dir[i][0];
            next.y = tmp.y+dir[i][1];
            if(next.x<1||next.x>n||next.y<1||next.y>n||vis[next.x][next.y]) 
                continue;
            next.d = tmp.d + map[next.x][next.y];
            que.push(next);
        }
    }
}

__int64 solve(int x,int y)
{
    if(dp[x][y] != -1) return dp[x][y];
    else {
        node next;
        dp[x][y] = 0;
        for(int i = 0;i < 4;i++) {
            next.x = x+dir[i][0];
            next.y = y+dir[i][1];
            if(next.x<1||next.x>n||next.y<1||next.y>n)
                continue;
            next.d = dis[next.x][next.y];
            if(next.d < dis[x][y]) 
                dp[x][y]+=solve(next.x,next.y);
        }
        return dp[x][y];
    }
}

int main()
{
    while(cin>>n)
    {
        memset(dp,-1,sizeof(dp));
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                cin>>map[i][j];
        dfs();
        /*测试最小距离 
        cout<<endl<<"~~~"<<endl;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++){
                cout<<dis[i][j]<<‘ ‘;
                if(j == n)
                    cout<<endl;
            }
        */
        dp[n][n] = 1;
        cout<<solve(1,1)<<endl;
    }
    return 0;
}