频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU 1078 FatMouse and Cheese(记忆化搜索)
2013-07-31 16:06:31           
收藏   我要投稿

题意:给定一幅图,每个点有一定权值,现在有一只老鼠在起始点(0,0),他能水平或者垂直移动1~k格之后,停在某点并获得权值,而且每次移动后所在的点,都要比刚离开的那个点的权值更大,求最多能获得多少权值。

分析:依旧是搜索,把条件分析清楚,dp[i][j] 表示从i,j出发能获得的最多的权值。

 

#include<cstdio>   
#include <iostream>   
#include <cstring>   
#include <cmath>   
#include <algorithm>   
# define MAX 111   
using namespace std;  
  
int dirx[4] = {1,-1,0,0} ;  
int diry[4] = {0,0,1,-1} ;  
int n,k;  
int map[MAX][MAX];  
long long dp[MAX][MAX];  
int vis[MAX][MAX];  
  
bool inside(int x,int y) {  
    if(x < 0 || x >=n || y < 0 || y >= n) {  
        return false;  
    }  
    return true;  
}  
  
void init() {  
  
    memset(vis,0,sizeof(vis));  
    memset(dp,0,sizeof(dp));  
}  
  
long long dfs(int x,int y) {  
    if(dp[x][y] != 0) return dp[x][y];  
    vis[x][y] = 1;  
  
    long long maxx = -1;  
    for(int i=0; i<4; i++) {  
        for(int j=1; j<=k; j++) {  
            int xx = x + dirx[i] * j;  
            int yy = y + diry[i] * j;  
            if(inside(xx,yy) && vis[xx][yy] == 0 && map[xx][yy] > map[x][y]) {  
                maxx = max(maxx,dfs(xx,yy));  
                vis[xx][yy] = 0;  
            }  
        }  
    }  
    if(maxx == -1) {  
        return dp[x][y] = map[x][y];  
    }  
    return dp[x][y] = maxx + map[x][y];  
}  
  
int main() {  
    int i,j;  
    while(cin >> n >> k) {  
        if(n == -1 && k == -1) {  
            break;  
        }  
        init();  
        for(i=0; i<n; i++) {  
            for(j=0; j<n; j++) {  
                scanf("%d",&map[i][j]);  
            }  
        }  
        cout << dfs(0,0) << endl;  
    }  
    return 0;  
}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 记忆
上一篇:C++ Map使用
下一篇:hdu 1072 Nightmare (bfs+贪心)
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站