uva 10285 Longest Run on a Snowboard （记忆化搜索）

uva 10285 Longest Run on a Snowboard题目大意：给出一张n*m的雪地地图，每格标注的是该点的高度。从地势高的地方可以滑到地势低的地方（只能上下左右滑），问最长的滑雪距离。解题思路：逐一访问各点，若该点没有被访问过，则进行DFS找出该点为滑雪起始点的最长滑雪距离，用dp数组记录，若该点已被访问过，则返回其对应的dp数组记录的值。;char s[N];int snow[N][N], dp[N][N];int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int n, m, Max;int DFS(int x, int y) {int px, py, ans = 1, t;if (dp[x][y] != -1) return dp[x][y];for (int i = 0; i < 4; i++) {px = x + dir[i][0];py = y + dir[i][1];if (px < 0 || py < 0) continue;if (px >= n || py >= m) continue;if (snow[px][py] < snow[x][y]) {t = DFS(px, py);if (t + 1 > ans) ans = t + 1;}}return dp[x][y] = ans;}int main() {int T;scanf(“%d”, &T);while (T–) {memset(dp, -1, sizeof(dp));Max = 0;scanf(“%s”, s);scanf(“%d %d”, &n, &m);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf(“%d”, &snow[i][j]);}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int temp = DFS(i, j);if (temp > Max) {Max = temp;}}}printf(“%s: %d\n”, s, Max);}return 0;}

，千万个不眠的夜里，你一直让我感动，只是因为相信有个人会爱我一生一世。