首页 > 代码库 > hdu1428 记忆化搜索
hdu1428 记忆化搜索
注意:
题目给的是你每个点的值 所以必须的先求出来每个点到终点的最小路径和 这里我是用bfs处理的 存在dis数组里
注意题意里说的 当前这个点能走到下个点的条件是当前点到终点的值比下个点到终点的值大
#include<stdio.h> #include<string.h> #include<queue> #include<iostream> using namespace std; #define INF 0x3f3f3f3f __int64 dp[55][55],n; int mark[55][55],tie[55][55]; int dir[4][2]={0,1,0,-1,1,0,-1,0},dis[55][55]; int max(int a,int b) { return a>b?a:b; } int min(int a,int b) { return a<b?a:b; } struct node { int x,y; }a,b; int bfs() { a.x=n; a.y=n; queue<node>q; q.push(a); while(!q.empty()) { b=q.front(); q.pop(); for(int i=0;i<4;i++) { a.x=b.x+dir[i][0]; a.y=b.y+dir[i][1]; if(a.x<1||a.x>n||a.y<1||a.y>n) continue; if(dis[a.x][a.y]>dis[b.x][b.y]+tie[a.x][a.y]) { dis[a.x][a.y]=dis[b.x][b.y]+tie[a.x][a.y]; q.push(a); } } } return 0; } __int64 dfs(int x,int y) { int i,j; for(i=0;i<4;i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; if(xx<1||xx>n||yy<1||y>n) continue; if(dis[x][y]<=dis[xx][yy]) continue; if(mark[xx][yy]==0) { mark[xx][yy]=1; dfs(xx,yy); } dp[x][y]+=dp[xx][yy]; } return dp[x][y]; } int main() { int i,j; while(~scanf("%d",&n)) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&tie[i][j]); memset(dis,INF,sizeof(dis)); dis[n][n]=tie[n][n]; bfs(); /*for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%d ",dis[i][j]); printf("\n"); }*/ memset(dp,0,sizeof(dp)); memset(mark,0,sizeof(mark)); mark[1][1]=1; dp[n][n]=1; printf("%I64d\n",dfs(1,1)); } return 0; }
hdu1428 记忆化搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。