【poj1088】 滑雪

http://poj.org/problem?id=1088 (题目链接)

题意

　　给出一个矩阵，任意选择一个起点，每次只能向周围4个格子中的值比当前格子小的格子移动，求最多能移动多少步。

Solution

　　其实很简单，将矩阵中的值进行排序，从小到大更新。比如说当前点（i，j），它只能由周围4个点走到，所以取最大值，而排序就保证了更新的顺序不会出错。

代码

// poj1088

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi 3.1415926535898

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

struct data {int w,r,c;}a[1000010];

int f[1010][1010],r,c,cnt,h[1010][1010];

bool cmp(data a,data b) {return a.w<b.w;}

int main() {

    scanf("%d%d",&r,&c);

    memset(h,0x7f,sizeof(h));

    for (int i=1;i<=r;i++)

        for (int j=1;j<=c;j++) {

            int w;

            scanf("%d",&w);h[i][j]=w;

            a[++cnt].w=w;a[cnt].r=i;a[cnt].c=j;

        }

    sort(a+1,a+1+cnt,cmp);

    int ans=0;

    for (int i=1;i<=cnt;i++) {

        int x=a[i].r,y=a[i].c,w=a[i].w;

        if (w>h[x-1][y]) f[x][y]=max(f[x][y],f[x-1][y]+1);

        if (w>h[x][y-1]) f[x][y]=max(f[x][y],f[x][y-1]+1);

        if (w>h[x+1][y]) f[x][y]=max(f[x][y],f[x+1][y]+1);

        if (w>h[x][y+1]) f[x][y]=max(f[x][y],f[x][y+1]+1);

    }

    for (int i=1;i<=r;i++)

        for (int j=1;j<=c;j++) ans=max(ans,f[i][j]);

    printf("%d",ans+1);

    return 0;

}