hdu1428漫步校园( 最短路+BFS（优先队列）+记忆化搜索（DFS）)
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
#include<stdio.h> #include<iostream> #include<queue> using namespace std; typedef struct nn { int dist,x,y; friend bool operator <(nn n1,nn n2) { return n1.dist>n2.dist; } }node; int map[55][55],N[55][55],n; __int64 dp[55][55]; int dir[4][2]={1,0,-1,0,0,1,0,-1}; void BFS()//求每一点到终点的最小距离，从终点出发 { priority_queue<node> Q; node q,p; int i,tx,ty; q.x=q.y=n; q.dist=map[n][n]; Q.push(q); N[n][n]=map[n][n]; while(!Q.empty()) { q=Q.top(); Q.pop(); for(i=0;i<4;i++) { tx=q.x+dir[i][1];ty=q.y+dir[i][0]; if(tx>0&&tx<=n&&ty>0&&ty<=n) if(N[ty][tx]==-1||N[ty][tx]>N[q.y][q.x]+map[ty][tx])//当前点还没有用过或是用过了又不是最小距离，才执行 { p.x=tx;p.y=ty; p.dist=N[q.y][q.x]+map[ty][tx]; N[ty][tx]=p.dist; Q.push(p); } } }//printf("%d",N[1][1]); } __int64 DFS(int x,int y)//记忆化搜索，每点到终点满足条件有多少种走法 { int e,tx,ty; if(dp[y][x]>0)//当前的点己经走过了，直接反回当前的点有多少种走法 return dp[y][x]; if(x==n&&y==n) return 1; for(e=0;e<4;e++)//当前点所走的范围，所以会把它所有范围的点到终点的走法全加起来 { tx=x+dir[e][1];ty=y+dir[e][0]; if(ty>0&&ty<=n&&tx>0&&tx<=n) if(N[y][x]>N[ty][tx])//当前的点到终点距离要大于它将要走的点到终点的距离，有多少种走法 { dp[y][x]+=DFS(tx,ty); } } return dp[y][x];//当前点的范围走完时，反回给它所在其他点的范围 } int main() { int i,j; __int64 k; while(scanf("%d",&n)>0) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&map[i][j]); N[i][j]=-1;dp[i][j]=0; } BFS(); /*for(i=1;i<=n;i++) {printf("\n"); for(j=1;j<=n;j++) printf("%d ",N[i][j]); }*/ k=DFS(1,1); printf("%I64d\n",k); } } #include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
typedef struct nn
{
int dist,x,y;
friend bool operator <(nn n1,nn n2)
{
return n1.dist>n2.dist;
}
}node;
int map[55][55],N[55][55],n;
__int64 dp[55][55];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void BFS()//求每一点到终点的最小距离，从终点出发
{
priority_queue<node> Q;
node q,p;
int i,tx,ty;
q.x=q.y=n; q.dist=map[n][n];
Q.push(q); N[n][n]=map[n][n];
while(!Q.empty())
{
q=Q.top();
Q.pop();
for(i=0;i<4;i++)
{
tx=q.x+dir[i][1];ty=q.y+dir[i][0];
if(tx>0&&tx<=n&&ty>0&&ty<=n)
if(N[ty][tx]==-1||N[ty][tx]>N[q.y][q.x]+map[ty][tx])//当前点还没有用过或是用过了又不是最小距离，才执行
{
p.x=tx;p.y=ty; p.dist=N[q.y][q.x]+map[ty][tx];
N[ty][tx]=p.dist;
Q.push(p);
}
}
}//printf("%d",N[1][1]);
}
__int64 DFS(int x,int y)//记忆化搜索，每点到终点满足条件有多少种走法
{
int e,tx,ty;
if(dp[y][x]>0)//当前的点己经走过了，直接反回当前的点有多少种走法
return dp[y][x];
if(x==n&&y==n)
return 1;
for(e=0;e<4;e++)//当前点所走的范围，所以会把它所有范围的点到终点的走法全加起来
{
tx=x+dir[e][1];ty=y+dir[e][0];
if(ty>0&&ty<=n&&tx>0&&tx<=n)
if(N[y][x]>N[ty][tx])//当前的点到终点距离要大于它将要走的点到终点的距离，有多少种走法
{
dp[y][x]+=DFS(tx,ty);
}
}
return dp[y][x];//当前点的范围走完时，反回给它所在其他点的范围
}
int main()
{
int i,j;
__int64 k;
while(scanf("%d",&n)>0)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
N[i][j]=-1;dp[i][j]=0;
}
BFS();
/*for(i=1;i<=n;i++)
{printf("\n");
for(j=1;j<=n;j++)
printf("%d ",N[i][j]);
}*/
k=DFS(1,1);
printf("%I64d\n",k);
}
}
补充：软件开发 , C++ ,
