学步园

题意：一个 n x n 的矩阵(2=<n<=50)，矩阵中的每个元素代表在这个位置上要花的时间(0<t<=50)，现要从(1, 1) 去到(n, n)，在走的过程中，如果走一步，则到达的位置到(n, n)的最短路要比当前位置到达(n, n)的最短路要短。问到达(n, n)有多少种走法。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1428

——>>题目有点绕。。所说的最短路是从终点往回推的最短路。。

先 bfs 求出各点到(n, n)的最短路，再dp。。

状态：dp[i][j] 表示从 (i, j) 到(n, n)的路径数

#include <cstdio>
#include <queue>
#include <cstring>

using std::priority_queue;

const int MAXN = 50 + 10;
const int dx[] = {-1, 1,  0, 0};
const int dy[] = { 0, 0, -1, 1};

struct NODE
{
    int x;
    int y;
    long long t;

    NODE(int x = 0, int y = 0, long long t = 0) : x(x), y(y), t(t){}

    bool operator < (const NODE& e) const
    {
        return t > e.t;
    }
};

int n;
long long G[MAXN][MAXN];
long long Time[MAXN][MAXN];
long long dp[MAXN][MAXN];

void Read()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            scanf("%I64d", &G[i][j]);
        }
    }
}

void Bfs()
{
    priority_queue<NODE> qu;

    memset(Time, -1, sizeof(Time));
    qu.push(NODE(n, n, G[n][n]));
    Time[n][n] = G[n][n];
    while (!qu.empty())
    {
        NODE u = qu.top();
        qu.pop();
        for (int i = 0; i < 4; ++i)
        {
            int newx = u.x + dx[i];
            int newy = u.y + dy[i];
            if (newx >= 1 && newx <= n && newy >= 1 && newy <= n && Time[newx][newy] == -1)
            {
                Time[newx][newy] = u.t + G[newx][newy];
                qu.push(NODE(newx, newy, Time[newx][newy]));
            }
        }
    }
}

void Init()
{
    memset(dp, -1, sizeof(dp));
    dp[n][n] = 1;
}

long long Dp(int x, int y)
{
    long long& ans = dp[x][y];

    if (ans != -1) return ans;
    ans = 0;
    for (int i = 0; i < 4; ++i)
    {
        int newx = x + dx[i];
        int newy = y + dy[i];
        if (newx >= 1 && newx <= n && newy >= 1 && newy <= n && Time[newx][newy] < Time[x][y])
        {
            ans += Dp(newx, newy);
        }
    }

    return ans;
}

void Solve()
{
    printf("%I64d\n", Dp(1, 1));
}

int main()
{
    while (scanf("%d", &n) == 1)
    {
        Read();
        Bfs();
        Init();
        Solve();
    }

    return 0;
}

状态转移方程：dp[i][j] += dp[x][y]。。(i, j) ——> (x, y) ——> (n, n)。。