poj_1088

题目:

Description

Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 
 1  2  3  4 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

输出最长区域的长度。
Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output

25

 类型:这是一道BFS加上剪枝的题目【什么叫做剪枝可以看看poj_1579】,此处运用剪枝可以优化,减少运算量。

 分析:题目要求我们找到一个最长的线路,通过画解答树如下:

 图中的圆内数字表示高度,从左往右依次代表了坐标从(0,0)到(4,4)的点因为题目的解答树太大就不完全画出来了,大致的思路就是针对每一个点都画出可能的情况,每个结点的子结点最多就是四个(四个方向),对于边界的就应该少一个到两个,但是每个结点并不都是满足的,在图中用了红色字体标识出来了,表示高度上不满足要求。所以我们可以令f(x, y)表示在坐标(x,y)的地方的最长路径,得到针对每一个坐标如下的状态转移方程f(x,y) = max(f(x+1, y), f(x-1, y), f(x,y-1), f(x,y+1))+1,加上1不难理解就是子结点到父结点也是一个长度。这里再说明下剪枝,也就是在图中的情况,比如在左边的图中将会计算到高度2这个坐标的路径长情况,但是高度17也算了一次,这种情况在整个解答树中是会重复多次的,解决的方法就是如下:

直接利用前面已经计算出来的结果,就可以进行减少重复计算了; 这种思想也叫做记忆化搜索,也就是通过判断前面是否数据已经计算好了,如果已经计算好了就直接利用,这里的判断方式一般是根据数据是否等于我们一开始设定的初始值,比如0,-1等;

代码如下:

#include<stdio.h>
#define MAX 100

int r, c;
int Matrix[MAX][MAX];
int count[MAX][MAX];

int direction[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};//代表了四个方向

int height(int x, int y) {
    int next_x, next_y, k, max_len;
    //避免重复运算;因为前面的点可能已经算出了这个点的值
    if(count[x][y] > 0) //这里用count[][] > 0是因为count一开始就为静态变量,编译器会自动初始化它的全部元素为0
        return count[x][y];

    max_len = 0;
    for(k = 0; k < 4; ++k) {
        next_x = x + direction[k][0];
        next_y = y + direction[k][1];
        if(next_x >= 0 && next_y >= 0 && next_x < r && next_y < c) {
            if(Matrix[x][y] > Matrix[next_x][next_y]) {
                max_len = max_len > height(next_x, next_y) ? max_len : height(next_x, next_y);
            }
        }
    }
    count[x][y] = max_len + 1;
    return count[x][y];
}


int main() {
    int i, j, max_len;
    scanf("%d%d", &r, &c);

    for(i = 0; i < r; ++i) 
        for(j = 0; j < c; ++j)
            scanf("%d", &Matrix[i][j]);
    max_len = 0;
    for(i = 0; i < r; ++i) {
        for(j = 0; j < c; ++j) {
            if(max_len < height(i, j))
                max_len = height(i, j);
        }
    }
    printf("%d
", max_len);
}
原文地址:https://www.cnblogs.com/kinthon/p/4489476.html