HDU 1078 FatMouse and Cheese(记忆化搜索)

题意：给定一幅图，每个点有一定权值，现在有一只老鼠在起始点（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;  
}  

补充：软件开发 , C++ ,

上一个：hdu 1072 Nightmare (bfs+贪心)
下一个：C++ Map使用