POJ_1088_滑雪
http://poj.org/problem?id=1088记忆化搜索
Description
Michael喜欢滑雪这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1234 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000
Output
输出最长区域的长度
#include <iostream>using namespace std;int map, dp, r, c;int x_move = {-1, 0, 1, 0};int y_move = {0, -1, 0, 1};bool visited;int dp_dfs (int x, int y){if (dp > 0) //记录有值，立刻返回return dp;int i, tx, ty;for (i = 0; i < 4; i++){tx = x + x_move;ty = y + y_move;if (tx >= 0 && ty >= 0 && tx < r && ty < c){if (!visited && map < map){visited = true;dp = max (dp, dp_dfs (tx, ty) + 1); //转移方程，4个方向都有了visited = false;}}}return dp; //返回当前步数}int main(){int i, j, maxs;while (scanf ("%d%d", &r, &c) != EOF){for (i = 0; i < r; i++)for (j = 0; j < c; j++)scanf ("%d", map+j);memset (dp, 0, sizeof(dp));maxs = 0;for (i = 0; i < r; i++){for (j = 0; j < c; j++){int temp = dp_dfs (i, j);//cout << temp << endl;if (maxs < temp) //枚举找到最大值maxs = temp;}}printf ("%d\n", maxs+1);}return 0;}
页:
[1]