[每日算法]滑雪

题目描述

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（从 24 开始，在 1 结束）。当然 25－24－23－…－3－2－1 更长。事实上，这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 R 和列数 C。下面是 R 行，每行有 C 个数，代表高度(两个数字之间用 1 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

输入输出样例

样例#1	输出#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

说明/提示

对于100% 的数据，1≤R,C≤100。

题解

很明显这是个动态规划问题。把每个点存为一个元素，则它的最长路径来自它的上下左右四边的最长的最长路+1。那么可以得到动态转移方程为f【i】【j】=max(f【i】【j】,f【i-1】【j】+1,f【i+1】【j】+1,f【i】【j-1】+1,f【i】【j+1】+1)（h[now]>h[next])；动态规划要考虑无后效性。因此需要先计算较低的点，对后面算高的点没有影响。即在优先级队列中，高度越小，优先级就越高。

源代码

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

struct Node
{
    int x;        //第一维坐标
    int y;        //第二维坐标
    int height;    //高度
    Node(){};
    Node(int x0, int y0, int h) :x(x0), y(y0), height(h) {};
};

//高度越小，优先级越高
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.height > b.height;
    }
};

int sking(int m,int n,priority_queue<Node, vector<Node>, cmp> tempQueue, int (*datas)[101], int (*result)[101])
{
    Node node;
    int x, y;
    int maxL = 0;
    //用动态规划的方法，从高度最小的节点开始处理
    while (!tempQueue.empty())
    {
        node = tempQueue.top();
        tempQueue.pop();
        x = node.x;
        y = node.y;
        //上下左右四个位置逐个处理
        //上
        if (x - 1 >= 0)
        {
            if (datas[x][y] > datas[x - 1][y])
            {//如果这个节点比上面高，那么可以向上划,取较大值
                result[x][y] = max(result[x][y], result[x - 1][y] + 1);
            }
        }
        //下
        if (x + 1 <= m - 1)
        {
            if (datas[x][y] > datas[x + 1][y])
            {//如果这个节点比下面高，那么可以向下划
                result[x][y] = max(result[x][y], result[x + 1][y] + 1);
            }
        }
        //左
        if (y - 1 >= 0)
        {
            if (datas[x][y] > datas[x][y - 1])
            {//如果这个节点比左面高，那么可以向左划
                result[x][y] = max(result[x][y], result[x][y - 1] + 1);
            }
        }
        //右
        if (y + 1 <= n - 1)
        {
            if (datas[x][y] > datas[node.x][node.y + 1])
            {//如果这个节点比下面高，那么可以向上划
                result[x][y] = max(result[x][y], result[x][y + 1] + 1);
            }
        }
        if (result[x][y] > maxL) maxL = result[x][y];
    }
    return maxL;
}

int main()
{
    int m, n, hei, i, j;
    //将数据读入一个优先级队列和数据数组中
    //创建动态二维数组存放高度
    cin >> m >> n;
    int datas[101][101];
    //创建动态二维数组存放最大长度

    int result[101][101];
    for (i = 0;i < m;i++)
    {
        for (j = 0;j < n;j++)
        {
            result[i][j] = 1;
        }
    }

    priority_queue<Node, vector<Node>, cmp> tempQueue;
    for (i = 0;i < m;i++)
    {
        for (j = 0;j < n;j++)
        {
            cin >> hei;
            Node* tempNode = new Node(i, j, hei);
            tempQueue.push(*tempNode);        //存入优先级队列
            datas[i][j] = hei;                //存入数组
        }
    }

    cout << sking(m, n, tempQueue, datas, result);

    //释放内存
    return 0;
}