首页 > 代码库 > hdu 1428 漫步校园 (最短路+记忆化搜索)

hdu 1428 漫步校园 (最短路+记忆化搜索)

2024-07-24 14:59:16   220人阅读

漫步校园

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=<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
 

刚开始竟然把题意搞错了，"想把每个方格映射为一个点，一个格子到下一个格子的距离为当前格子的时间"。。

后来一想，这样，a->b和 b->a的距离就不一样了。有点想当然了。。。

正确的方法是：直接把格子作为一个点，求（n,n）点到各个点的最短路，然后，按照条件搜索就行了。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
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<n;i++)
    {
        for(j=0;j<n;j++)
        {
            mark[i][j]=0;
            num[i][j]=-1;
            dis[i][j]=inf;
        }
    }
}
void spfa(int s)
{
    int i,di,dj,x,y;
    queue<node>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<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        spfa(n*n-1);      
        num[n-1][n-1]=1;          //终点是一种方案
        printf("%I64d\n",dfs(0,0));
    }
    return 0;
}





hdu 1428 漫步校园 (最短路+记忆化搜索)


联系
我们