漫步校园
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3023 Accepted Submission(s): 917
Problem Description LL最近沉迷于AC不能自拔，每天寝室、机房两点一线。由于长时间坐在电脑边，缺乏运动。他决定充分利用每次从寝室到机房的时间，在校园里散散步。整个HDU校园呈方形布局，可划分为n*n个小方格，代表各个区域。例如LL居住的18号宿舍位于校园的西北角，即方格(1,1)代表的地方，而机房所在的第三实验楼处于东南端的(n,n)。因有多条路线可以选择，LL希望每次的散步路线都不一样。另外，他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是，所有满足要求的路线一共有多少条。你能告诉他吗?
Input 每组测试数据的第一行为n(2=
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
刚开始竟然把题意搞错了，"想把每个方格映射为一个点，一个格子到下一个格子的距离为当前格子的时间"。。
后来一想，这样，a->b和 b->a的距离就不一样了。有点想当然了。。。
正确的方法是：直接把格子作为一个点，求（n,n）点到各个点的最短路，然后，按照条件搜索就行了。
#include
#include
#include
#include
#include
using namespace std; #define LL __int64 #define N 55 const int inf=(int)1e9; int a[N][N],n; LL num[N][N]; //存储每个格子的可行路线数 int dis[N][N],mark[N][N]; //记录每个方格到终点的最短时间 int dir[4][2]={0,1,0,-1,-1,0,1,0}; struct node { int x,y,t; }; void inti() { int i,j; for(i=0;i
q; inti(); node cur,next; x=cur.x=s/n; y=cur.y=s%n; cur.t=a[x][y]; dis[x][y]=cur.t; q.push(cur); while(!q.empty()) { cur=q.front(); q.pop(); x=cur.x; y=cur.y; mark[x][y]=0; for(i=0;i<4;i++) { next.x=di=cur.x+dir[i][0]; next.y=dj=cur.y+dir[i][1]; if(di<0||di>=n||dj<0||dj>=n) continue; int tmp=dis[x][y]+a[di][dj]; if(dis[di][dj]>tmp) { next.t=dis[di][dj]=tmp; if(!mark[di][dj]) { mark[di][dj]=1; q.push(next); // printf("%d %d %d\n",next.x,next.y,next.t); } } } } } LL dfs(int x,int y) { if(num[x][y]!=-1) return num[x][y]; int i,di,dj; LL tmp=0; for(i=0;i<4;i++) { di=dir[i][0]+x; dj=dir[i][1]+y; if(di<0||di>=n||dj<0||dj>=n) continue; if(dis[x][y]>dis[di][dj]) tmp+=dfs(di,dj); } return num[x][y]=tmp; } int main() { int i,j; while(scanf("%d",&n)!=-1) { for(i=0;i