HDU-1078.FatMouseandCheese(线性dp + dfs)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

本题大意：在一个n * n的迷宫内进行移动，左上角为初始位置，每次可以走的步数不能超过m，并且每次走的方格上面的数字要大于前一次走的放个数字，不能走到格子外面，问如何能使得到的数字和最大。

本题思路：dfs记忆化搜即可。

参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std; int n, m;
const int maxn = 1e2 + ;
int maze[maxn][maxn], dp[maxn][maxn], dir[][] = {{,},{-,},{,},{,-}}; int dfs(int x, int y) {
int ans = ;
if(!dp[x][y]) {
for(int i = ; i <= m; i ++) {
for(int j = ; j < ; j ++) {
int dx = x + dir[j][] * i;
int dy = y + dir[j][] * i;
if(dx < || dy < || dx > n || dy > n) continue;
if(maze[dx][dy] > maze[x][y]) ans = max(ans, dfs(dx, dy));
}
}
dp[x][y] = ans + maze[x][y];
}
return dp[x][y];
} int main () {
ios :: sync_with_stdio (false);
while(cin >> n >> m) {
memset(dp, , sizeof dp);
if(n == - && m == -) break;
for(int i = ; i <= n; i ++)
for(int j = ; j <= n; j ++)
cin >> maze[i][j];
cout << dfs(, ) << endl;
}
return ;
}