NYOJ 10 Skitting

NYOJ 10 求最长下降坡度.


描述
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更长。事实上，这是最长的一条。

输入
第一行表示有几组测试数据，输入的第二行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。 后面是下一组数据； 输出 输出最长区域的长度。 样例输入 1 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 样例输出 25 下面的代码有误,一直Wrong Answer,但是同样的代码在北大POJ却一次通过,估计是输出的问题,不影响解题思路. 读取多组数据类似,对于每一组的处理思路:设置一个数组q记录每个元素对应的最长路径.读完数据后,扫一次,将当前元素比上下左右都小的位置在q中标记为1(也就是这个点的路径长度是1),作为递归时的出口. 然后将数据p,数组q,数组尺寸(row,col)和需要求的位置(r,c)作为参数传递给getLen子函数,用来设置q(r,c).如果已经设置,直接返回长度;否则,对于这个位置,检查上下左右4个数据,并将最大值设置为q(r,c). 检查上下左右数据时,如果数据数组p中该位置pos比当前位置小(可以滑过去),并且长度数组q中该位置已经设置为x,直接返回x+1,否则递归1+getLen(pos).由于递归出口(数组中最小的值)已经设置好,所以搜索时的次数会随着程序运行不断减小,直至q中所有元素均被设置.然后找到最大的元素输出即可.

#include <iostream>
#include <fstream>
using namespace std;

#define max(a,b) (((a)>(b))?(a):(b))

// 用q来储存每个点的最长路径,加速查找速度
int getLen(int **p, int **q, int row, int col, int r, int c)
{
    if (r<0 || r>=row || c<0 || c>=col) return -1;
    if (q[r][c]!=-1) return q[r][c];

    int up, down, left, right;
    up = down = left = right = 1;

    // 边界检查
    if (r-1<0) up = -1;
    if (r+1>=row) down = -1;
    if (c-1<0) left = -1;
    if (c+1>col) right = -1;

    // 如果不是第一行,当前上路径=上面元素的路径长度+1,下面的down,left,right一样
    if (up!=-1)
    {
        if (p[r-1][c]<p[r][c]) // 小于时可走
        {
            if (q[r-1][c]!=-1) up = 1+q[r-1][c]; // 上面元素路径已经计算过
            else up = 1+getLen(p,q,row,col,r-1,c); // 否则,递归
        }
        else // 大于,只记录自身
        { up = 1; }
    }
    else
    { up = 1; }

    if (down!=-1)
    {
        if (p[r+1][c]<p[r][c])
        {
            if (q[r+1][c]!=-1) down = 1+q[r+1][c];
            else down = 1+getLen(p,q,row,col,r+1,c);
        }
        else
        { down = 1; }
    }
    else
    { down = 1; }

    if (left!=-1)
    {
        if (p[r][c-1]<p[r][c])
        {
            if (q[r][c-1]!=-1) left = 1+q[r][c-1];
            else left = 1+getLen(p,q,row,col,r,c-1);
        }
        else
        { left = 1; }
    }
    else
    { left = 1; }

    if (right!=-1)
    {
        if (p[r][c+1]<p[r][c])
        {
            if (q[r][c+1]!=-1) right = 1+q[r][c+1];
            else right = 1+getLen(p,q,row,col,r,c+1);
        }
        else
        { right = 1; }
    }
    else
    { right = 1; }

    // 当前路径等于上下左右最长的,更新q数组
    q[r][c] = max(max(up,down),max(left,right));

    return q[r][c];
}

int main()
{
    ifstream cin("data.txt");
    int n,row,col,i,j;
    cin >> n;
    int **p,**q;
    int up,down,left,right,mlen,curlen;
    while (n-->0)
    {
        // 读取当前case数据
        cin >> row >> col;
        p = new int *[row];
        q = new int *[row];
        for (i=0;i<row;i++)
        {
            p[i] = new int[col];
            q[i] = new int[col];
            for (j=0;j<col;j++)
            {
                cin >> p[i][j];
                q[i][j] = -1;
            }
        }

        // set所有最小值点为1,作为子函数递归的出口
        for (i=0;i<row;i++)
        {
            for (j=0;j<col;j++)
            {
                up = down = left = right = 0;
                if (i-1<0) up = -1;
                if (i+1>=row) down = -1;
                if (j-1<0) left = -1;
                if (j+1>=col) right = -1;
                if (up!=-1 && p[i-1][j]>p[i][j]) up = -1;
                if (down!=-1 && p[i+1][j]>p[i][j]) down = -1;
                if (left!=-1 && p[i][j-1]>p[i][j]) left = -1;
                if (right!=-1 && p[i][j+1]>p[i][j]) right = -1;
                // 上下左右都比当前位置大,置1
                if (up==-1 && down==-1 && left==-1 && right==-1) q[i][j] = 1;
            }
        }

        // 寻找最长路径
        mlen = 0; curlen = 0;
        for (i=0;i<row;i++)
        {
            for (j=0;j<col;j++)
            {
                curlen = getLen(p,q,row,col,i,j);
                if (curlen>mlen) { mlen = curlen; }
            }
        }

        cout << mlen << endl;

        for (i=0;i<row;i++)
        {
            delete[] p[i];
            delete[] q[i];
        }
        delete[] p;
        delete[] q;
    }
    return 0;
}