浙江财经大学
信工学院ACM集训队

HDU 1428 漫步校园(BFS+记忆化DFS)

本文由 Ocrosoft 于 2016-07-07 9:05:23 发表

漫步校园

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3957    Accepted Submission(s): 1218

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
 

Solution

“从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近”

这句话的意思是:从A走到B之后,一定要离目标更近。例如A离(n,n)是1,B离(n,n)是2,那么就不能去B。

用BFS和优先队列从(n,n)开始,找出从(n,n)到每个点的最小距离,因为从那个点到(n,n)和从(n,n)是一个意思。找出最小距离后,记忆化DFS找出满足条件的路数量。看讨论区里好像说dp数组要开long long。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
int n;
int mp[55][55];
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
int vis[55][55];
long long dp[55][55];
struct node
{
    int x,y;
    int time;
    bool operator <(const node a) const
    {
        return time>a.time;
    }
    bool check()
    {
        if(x<=0||y<=0||x>n||y>n)return 1;
        return 0;
    }
} s,t;
void bfs()
{
    ms(vis);
    vis[n][n]=mp[n][n];
    bool f[55][55];
    ms(f);
    f[n][n]=1;
    priority_queue<node> q;
    s.x=n,s.y=n,s.time=mp[n][n];
    q.push(s);
    while(!q.empty())
    {
        s=q.top();
        q.pop();
        for(int i=0; i<4; i++)
        {
            t=s,t.x+=dir[i][0],t.y+=dir[i][1];
            if(t.check())continue;
            if(f[t.x][t.y])continue;
            t.time+=mp[t.x][t.y];
            vis[t.x][t.y]=t.time;
            f[t.x][t.y]=1;
            q.push(t);
        }
    }
}
long long dfs(int x,int y)
{
    if(dp[x][y]>0)return dp[x][y];
    for(int i=0; i<4; i++)
    {
        int nx=x+dir[i][0],ny=y+dir[i][1];
        if(nx<=0||ny<=0||nx>n||ny>n)continue;
        if(vis[nx][ny]>=vis[x][y])continue;
        dp[x][y]+=dfs(nx,ny);
    }
    return dp[x][y];
}
int main()
{
    while(cin>>n)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                cin>>mp[i][j];
        bfs();
        /*
                for(int i=1;i<=n;i++)
                {
                    for(int j=1;j<=n;j++)
                    {
                        printf(" %d",vis[i][j]);
                    }
                    printf("\n");
                }
        */
        ms(dp);
        dp[n][n]=1;
        dfs(1,1);
        printf("%I64d\n",dp[1][1]);
    }
    return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 1428 漫步校园(BFS+记忆化DFS)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址