首页 > 代码库 > uva10285 - Longest Run on a Snowboard(记忆化搜索)
uva10285 - Longest Run on a Snowboard(记忆化搜索)
题目:uva10285 - Longest Run on a Snowboard(记忆化搜索)
题目大意:给出N * N的矩阵,要求找到一条路径,路径上的值是递减的,求这样的路径的最长长度。
解题思路:记忆话搜索。因为要求最长的路径那么就需要将所有的这样的路径找出,但是直接dfs会超时的。对于同一个位置,从这个点出发的最长路径长度是固定的。所以在找的时候就要将这个位置的最长路径算出来并且保存下来。一开始还担心会走回头路就是一直兜圈子。但是后面发现能往右走就不可能在从右边的那个位置走回去,因为路径上的值是要求递减的。
dp【x】【y】代表从x,y这个位置开始能够走的最长的路径长度。
代码:
#include <cstdio> #include <cstring> const int N = 105; const int M = 4; const int dir[M][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; int G[N][N]; int dp[N][N]; char name[N * 10]; int r, c; int Max (const int a, const int b) { return a > b? a: b; } int DP (int x, int y) { int& ans = dp[x][y]; if (ans != -1) return ans; int newx, newy; for (int i = 0; i < M; i++) { newx = x + dir[i][0]; newy = y + dir[i][1]; if (newx < 0 || newx >= r || newy < 0 || newy >= c) continue; if (G[x][y] > G[newx][newy]) ans = Max (ans, DP (newx, newy) + 1); //从这个位置开始四个方向的最长长度取最大值 } if (ans == -1) //这个点走不出去 ans = 1; return ans; } int main () { int t; scanf ("%d", &t); while (t--) { scanf ("%s%d%d", name, &r, &c); for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) scanf ("%d", &G[i][j]); memset (dp, -1, sizeof (dp)); int ans = -1;
for (int i = 0; i < r; i++) 从每个位置开始走都是有可能的取得最长路径 for (int j = 0; j < c; j++) ans = Max (ans, DP(i, j)); printf ("%s: %d\n", name, ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。