POJ1088

题目：滑雪
链接：

思路：先对所有的高度升序排列，然后从最低点开始遍历整幅地图，考察当前点(x, y)四周的四个点，如果他们的路径长度
小于当前点路径+1，那么就更新该点的路径为 length[x][y] + 1。 思路很简单，初始化路径长度全为1，就可以了。


源码：

#include <iostream>
#include <cstdlib>

using namespace std;

struct Node {
    int h;
    int x;
    int y;
};

#define MAX 10000
#define ROW 100
#define COL 100

Node list[MAX];
int length[ROW][COL];
int land[ROW][COL];

int row, col;

int cmp(const void *a, const void *b) {
    return ((Node*)a)->h - ((Node*)b)->h;
}

void init() {
    for (int i=0; i<row; i++) {
        for (int j=0; j<col; j++) {
            cin >> land[i][j];
            int id = i*col + j;
            list[id].h = land[i][j];
            list[id].x = i;
            list[id].y = j;
            length[i][j] = 1;
        }
    }
    qsort(list, row*col, sizeof(Node), cmp);
}

int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int findMaxLength() {
    int maxLength = 1;
    for (int n=0; n<row*col; n++) {
        for (int i=0; i<4; i++) {
            int x = list[n].x + dir[i][0];
            int y = list[n].y + dir[i][1];
            if (x>=0 && x<row && y>=0 && y<col) {
                int curLen = length[list[n].x][list[n].y];
                if (land[x][y]>list[n].h && curLen+1>length[x][y]) {
                    length[x][y] = curLen + 1;
                    if (length[x][y] > maxLength)
                        maxLength = length[x][y];
                }
            }
        }
    }
    return maxLength;
}

int main() {
    while (cin >> row >> col) {
        init();
        cout << findMaxLength() << endl;
    }
    return 0;
}