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
?
题意：每个点就是一个区域,假如这个区域有一个属性K就是这个区域到机房的最短距离,那么LL只能从K大的向K小的区域走(相同也无法走),问一共有几种走法.
?
分析:
由于地图规模达到50×50,直接dfs暴力强搜绝对超时,而且从答案上走法可达到2^63亦可知道,一条条的暴力强搜必然超时.
这个时候我们可以考虑记忆化搜索(dp+搜索).
(1)先把每个点到机房的最短距离求出来,这个可以使用最短路径算法(Dijjstra.SPFA),也可以用dp,还可以用bfs,以及优先队列.(只不过这题我用Dijkstra处理的时候不知道是姿势不对还是怎么的,超时了,按道理最大规模为2500个点,Dijskstra的时间复杂度为O(n^2)应该也不会超时,搞不懂..)
(2)预处理完,把每个点到机房的最短距离存储到一个二维数组中dis[ ][ ];
(3)我们知道走的规矩是只能从K大向K小的走,那么假如其中一条路线中的A,B两点,那么A,B两点的路线方向唯一.所以我们根据这点可以得出一个定理：
一个点到机房的有效路径条数等于它四周相邻的点的条数之和.
这个时候我们就把搜索的时间规模降到的地图大小也就是O(n^2);
?
四种预处理每个点到机房的最短距离的代码():
?
1.Dijkstra (存储在 visit [ ] [ ] )
?
#include
#include
int time[2501][2501],map[51][51],n,visit[51][51]; int a[4][2]={0,1,1,0,0,-1,-1,0}; int main() { int i,j; while(scanf("%d",&n)!=EOF) { for(i=0;i
dis[u]+time[u][j]) dis[j]=dis[u]+time[u][j]; } } } for(i=0;i
?
2.dp (存储在 visit [ ] [ ] )
?
#include
#include
int map[51][51],n,visit[51][51]; int a[4][2]={0,1,1,0,0,-1,-1,0}; int main() { int i,j,flag,k,tx,ty; while(scanf("%d",&n)!=EOF) { for(i=0;i
=0;i--) { for(j=n-1;j>=0;j--) { for(k=0;k<4;k++) { tx=i+a[k][0]; ty=j+a[k][1]; if(tx<0||tx>=n||ty<0||ty>=n) continue; if(visit[i][j]>visit[tx][ty]+map[i][j]) //判断一个点从四个方向上的最近路 flag=1,visit[i][j]=visit[tx][ty]+map[i][j]; //一旦有点的信息发生变化flag标记为1表示要继续判断一次. } } } } return 0; }
3.bfs (存储在dis[ ][ ])
?
?
#include
#include
#include
#include
using namespace std; typedef __int64 ss; #define maxx 100000000 struct node { ss x,y; }; ss n,t[4][2]={1,0,-1,0,0,1,0,-1}; ss dis[100][100],vist[100][100],map[100][100]; void dj() { queue
q; for(ss i=0;i<=n;i++) for(ss j=0;j<=n;j++) dis[i][j]=maxx; dis[n][n]=map[n][n]; memset(vist,0,sizeof(vist)); vist[n][n]=1; node tmp; tmp.x=n; tmp.y=n; q.push(tmp); while(!q.empty()) //主要思想是用信息发生变化的点去更新相邻的点的信息.由于队列中都是信息发生变化的不用向上面dp那样每个点都搜索. { node tmp1=q.front(); q.pop(); vist[tmp1.x][tmp1.y]=0; for(ss i=0;i<4;i++) { ss xx=tmp1.x+t[i][0]; ss yy=tmp1.y+t[i][1]; if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&dis[xx][yy]>dis[tmp1.x][tmp1.y]+map[xx][yy]) { dis[xx][yy]=dis[tmp1.x][tmp1.y]+map[xx][yy]; if(!vist[xx][yy]) { node tmp2; tmp2.x=xx; tmp2.y=yy; q.push(tmp2); vist[xx][yy]=1; //visit数组是表示那些点在队列中. } } } } }
?
?
4.优先队列 (存储在dis[ ][ ])(时间复杂度最小)
?
#include
#include
#include
using namespace std; int dis[51][51],map[51][51],k[4][2]={0,1,1,0,0,-1,-1,0},n; int visit[51][51]; struct node { int x,y,step; friend bool operator < (node a, node b) { return a.step > b.step;//结构体中，step小的优先级高 } }; priority_queue
q; int main() { int i,j,tx,ty; while(scanf("%d",&n)!=EOF) { for(i=0;i
=n||ty<0||ty>=n) continue; node tmp2; tmp2.x=tx; tmp2.y=ty; tmp2.step=tmp1.step+map[tx][ty]; q.push(tmp2); } } } return 0; }
?
?
?
记忆化搜索部分代码 (预处理在dis[ ][ ],搜索结果放在dp[ ][ ])
?
long long dp[51][51];
long long dfs(int x,int y)
{
if(dp[x][y])return dp[x][y];
int i,tx,ty;
for(i=0;i<4;i++)
{
tx=x+k[i][0];
ty=y+k[i][1];
if(tx<0||ty<0||tx>=n||ty>=n||dis[tx][ty]>=dis[x][y])
continue;
dp[x][y]+=dfs(tx,ty);
}
return dp[x][y];
}
int main()
{
int i,j,tx,ty;
while(scanf("%d",&n)!=EOF)
{
……
memset(dp,0,sizeof(dp));
dp[n-1][n-1]=1;
printf("%lld\n",dfs(0,0));
}
return 0;
}
Dijkstra预处理超时了,剩下的3个都是AC了的.
?