hdu1428 漫步校园

思路：有几条可到达的路线是很常规的dp，假设u->v ，那么dp[u]+=dp[v]

下一步一定要更加逼近终点而不是远离终点，用bfs去跑距(n,n)的最短路径。

本题可以与dijkstra堆优化过程中统计最短路条数进行对比：

本题：dp[i][j] (i,j)到终点的最短路条数；采用记忆化搜索方式，自下而上

dijkstra堆优化：dp[i] 代表起点到i的最短路条数；递推，自上而下

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=55;
typedef long long LL;
struct node
{
    int x,y;
    LL s;
    node(){}
    node(int x,int y,LL s):x(x),y(y),s(s){}
    bool operator<(const node &rhs)const
    {
        return s>rhs.s;
    }
};

int a[N][N];
int vis[N][N];
int dist[N][N];
LL dp[N][N];           //从i,j出发到终点有多少条路
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n;
void bfs()
{
    priority_queue<node> q;
    memset(dist,0,sizeof(dist));
    q.push(node(n,n,1));
    dist[n][n]=1;
    while(!q.empty())
    {
        node p=q.top();
        q.pop();
        int x=p.x, y=p.y;
        LL s=p.s;
        for(int i=0;i<4;++i)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!dist[nx][ny])
            {
                dist[nx][ny]=s+a[nx][ny];
                q.push(node(nx,ny,dist[nx][ny]));
            }
        }
    }
}

LL dfs(int x,int y)
{
    if(vis[x][y]) return dp[x][y];
    vis[x][y]=1;
    for(int i=0;i<4;++i)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&dist[nx][ny]<dist[x][y])
            {
                dp[x][y]+=dfs(nx,ny);
            }
        }
    return dp[x][y];

}
int main()
{
    while(cin>>n)
    {
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            {
                cin>>a[i][j];
            }
        bfs();
        dp[n][n]=1;
        cout<<dfs(1,1)<<endl;
    }


}