更多
黑客联盟 黑客软件
学生黑客联盟
您现在的位置:学生黑客联盟 > 编程频道 > 软件开发 > 浏览信息
C语言记忆化搜索_漫步校园(Hdu 1428)
时间:2015-03-20 22:06 来源:www.stuhack.com 作者:学盟网
Problem Description LL最近沉迷于AC不能自拔,每天寝室、机房两点一线。由于长时间坐在电脑边,缺乏运动。他决定充分利用每次从寝室到机房的时间,在校园里散散步。整个HDU校园呈方形布局,可划分为n*n个小方格,代表各个区域。例如LL居住的18号宿舍位于校

 

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 内容来自学生黑客联盟 

 

www.stuhack.com

题意:每个点就是一个区域,假如这个区域有一个属性K就是这个区域到机房的最短距离,那么LL只能从K大的向K小的区域走(相同也无法走),问一共有几种走法. 学盟网

 

内容来自学生黑客联盟

分析: 学盟网

由于地图规模达到50×50,直接dfs暴力强搜绝对超时,而且从答案上走法可达到2^63亦可知道,一条条的暴力强搜必然超时.

学生黑客联盟 www.stuhack.com

这个时候我们可以考虑记忆化搜索(dp+搜索). 学盟网

(1)先把每个点到机房的最短距离求出来,这个可以使用最短路径算法(Dijjstra.SPFA),也可以用dp,还可以用bfs,以及优先队列.(只不过这题我用Dijkstra处理的时候不知道是姿势不对还是怎么的,超时了,按道理最大规模为2500个点,Dijskstra的时间复杂度为O(n^2)应该也不会超时,搞不懂..)

学生黑客联盟 www.stuhack.com

(2)预处理完,把每个点到机房的最短距离存储到一个二维数组中dis[ ][ ];

学盟网

(3)我们知道走的规矩是只能从K大向K小的走,那么假如其中一条路线中的A,B两点,那么A,B两点的路线方向唯一.所以我们根据这点可以得出一个定理: 学生黑客联盟 www.stuhack.com

一个点到机房的有效路径条数等于它四周相邻的点的条数之和. 内容来自学生黑客联盟

这个时候我们就把搜索的时间规模降到的地图大小也就是O(n^2); 学盟网

 

本文来自学盟网(www.stuhack.com)

四种预处理每个点到机房的最短距离的代码(): 本文来自学盟网(www.stuhack.com)

 

学盟网

1.Dijkstra (存储在 visit [ ] [ ] )

www.stuhack.com

 

copyright www.stuhack.com

#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;idis[u]+time[u][j])
                       dis[j]=dis[u]+time[u][j];
               }
           }
        }
        for(i=0;i

  copyright www.stuhack.com

2.dp (存储在 visit [ ] [ ] )

www.stuhack.com

 

www.stuhack.com

#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;
} 
www.stuhack.com

3.bfs (存储在dis[ ][ ])

 

copyright www.stuhack.com

 

本文来自学盟网(www.stuhack.com)

#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()
{
    queueq;
    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数组是表示那些点在队列中.
                }
            }
        }
    }
}
 
学生黑客联盟 www.stuhack.com

  copyright www.stuhack.com

 

内容来自学生黑客联盟

4.优先队列 (存储在dis[ ][ ])(时间复杂度最小)

学盟网

  copyright www.stuhack.com

 

本文来自学盟网(www.stuhack.com)

#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_queueq; 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; } 

内容来自学生黑客联盟



 

www.stuhack.com

 本文来自学盟网(www.stuhack.com) 

 

www.stuhack.com

 

内容来自学生黑客联盟

记忆化搜索部分代码 (预处理在dis[ ][ ],搜索结果放在dp[ ][ ])

  学生黑客联盟 www.stuhack.com

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了的.

  www.stuhack.com

www.stuhack.com



本文标题:C语言记忆化搜索_漫步校园(Hdu 1428)

本文地址:http://www.stuhack.com/bc/ware/032014262.html

免责声明:本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。




百度钱包“落子

一个商户通过审核入驻百度钱包,将获得百度[查看详细]

移动搜索&发

移动搜索在移动端的创新和颠覆也为百度探索[查看详细]

张向宁:移动互联

张向宁回顾了他2002年提出的“互联网十大预[查看详细]

淘宝开卖二维码门

截至4月20日,淘宝已经售出车展的实体门票[查看详细]

百度钱包杀入移动

“百度钱包”将完成的 “搜索用户”与“消[查看详细]