题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1428
漫步校园
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
LL最近沉迷于AC不能自拔，每天寝室、机房两点一线。由于长时间坐在电脑边，缺乏运动。他决定充分利用每次从寝室到机房的时间，在校园里散散步。整个HDU校园呈方形布局，可划分为n*n个小方格，代表各个区域。例如LL居住的18号宿舍位于校园的西北角，即方格(1,1)代表的地方，而机房所在的第三实验楼处于东南端的(n,n)。因有多条路线可以选择，LL希望每次的散步路线都不一样。另外，他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是，所有满足要求的路线一共有多少条。你能告诉他吗?
Input
每组测试数据的第一行为n(2=<n<=50)，接下来的n行每行有n个数，代表经过每个区域所花的时间t(0<t<=50)(由于寝室与机房均在三楼，故起点与终点也得费时)。
Output
针对每组测试数据，输出总的路线数(小于2^63)。
Sample Input
3
1 2 3
1 2 3
1 2 3
3
1 1 1
1 1 1
1 1 1
Sample Output
1
6
Author
LL
解题思路：典型的记忆化搜索,先结合优先队列bfs记录每一个点到终点最短路线条数(完成记忆化),然后dfs搜索路线条数即可~~~
代码如下：
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int map[][], n;
int mark[][];
__int64 dp[][];
int dir[][] = { , , , -, , , -, };
struct node {
int x, y, time;
friend bool operator < (node x1, node x2){
//优先队列，时间小的先出队
return x1.time > x2.time;
}
};
void bfs(){
priority_queue<node>q;
node cur, next;
cur.x = n;//从（n，n）开始往前找，每次找最小时间到达（n，n）
cur.y = n;
cur.time = map[n][n];
mark[n][n] = ;
q.push(cur);
while (!q.empty()){
cur = q.top();
q.pop();
for (int i = ; i < ; i++){
next.x = cur.x + dir[i][];
next.y = cur.y + dir[i][];
if (next.x >= && next.x <= n&&next.y >= && next.y <= n&&!mark[next.x][next.y]){
mark[next.x][next.y] = ;
map[next.x][next.y] += cur.time;//在原数组记录每个点到终点的最短时间
next.time = map[next.x][next.y];
q.push(next);
}
}
}
}
__int64 dfs(int x, int y){
if (dp[x][y] > )return dp[x][y];
for (int i = ; i<; i++){
int v = x + dir[i][];
int u = y + dir[i][];
if (v >= && v <= n&&u >= && u <= n&&map[x][y]>map[v][u])//保证离终点原来越近
dp[x][y] += dfs(v, u);
}
return dp[x][y];
}
int main(){
int i, j;
while (scanf("%d", &n) != -){
memset(mark, , sizeof(mark));
for (i = ; i <= n; i++)
for (j = ; j <= n; j++)
scanf("%d", &map[i][j]);
bfs();
memset(dp, , sizeof(dp));
dp[n][n] = ;
printf("%I64d\n", dfs(, ));
}
return ;
}