uva 825 Walking on the Safe Side（动态规划：记忆化搜索）

本文主要是介绍uva 825 Walking on the Safe Side（动态规划：记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目的输入太蛋疼了...

题目本身倒是不难

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 1010
using namespace std;char str[MAXN];
int a[MAXN][MAXN], dp[MAXN][MAXN];int dfs(int i, int j) {if(dp[i][j] > 0)return dp[i][j];if(i<1 || j<1)return 0;int ans = 0;if(a[i-1][j] == 0)ans += dfs(i-1, j);if(a[i][j-1] == 0)ans += dfs(i, j-1);return dp[i][j] = ans;
}int main(void) {char ch;int T, x, tmp, m, n;scanf("%d", &T);while(T--) {getchar();scanf("%d%d", &m, &n);getchar();memset(a, 0, sizeof(a));for(int i=1; i<=m; ++i) {scanf("%d", &x);gets(str);int len = strlen(str);int cnt = 0;for(int j=0; j<=len; ++j) {if(str[j]-'0'>=0 && str[j]-'0'<=9)cnt = cnt*10+str[j]-'0';else {a[x][cnt] = 1;cnt = 0;}}}memset(dp, 0, sizeof(dp));dp[1][1] = 1;printf("%d\n", dfs(m, n));if(T) puts("");}return 0;
}

这篇关于uva 825 Walking on the Safe Side（动态规划：记忆化搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---