滑雪--POJ--1088

滑雪

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 36967		Accepted: 13013

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

Source

SHTSC 2002

解题思路：

定义 m[i][j] 表示从点 (i,j) 为起点滑行的最大长度。滑行时，选择周围可以滑行的且 m 值最大的方向滑行。如果 (i,j) 的四个相邻元素都存在的话，则可以得到如下递归式：

m[i][j]=Max(m[i][j-1],m[i][j+1],m[i-1][j],m[i+1][j]) +1

通过递归地计算 m[i][j-1],m[i][j+1],m[i-1][j] 和 m[i+1][j] 的值，找中四个中最大的一个，即是下一步滑行的位置，以此递归，直到不能继续滑行时返回。求解过程中，每求解到一个点的最大滑行长度则保存在数组m[i][j]中，因此不会重复求解同一个点的最大滑行长度。

（典型的记忆化搜索）

代码如下：

#include <iostream>

const int x[]={-1,0,1,0},y[]={0,1,0,-1}; //巧妙之处

int r,c;

int node[101][101];

int ppt[101][101];

//深搜

int dfs(int i,int j)

{

int k;

if(ppt[i][j]) //不为0，说明被访问过，直接返回

return ppt[i][j];

for(k=0;k<4;k++)//k值是为了决定x和y的方向(上下左右)

if(i+x[k]>=1 && i+x[k]<=r && j+y[k]>=1 && j+y[k]<=r) //没有越界

if( node[i+x[k]][j+y[k]]<node[i][j] ) //周围某点(上下左右之一,看循环的值了)高度小于当前点

if( ppt[i][j]< dfs(i+x[k],j+y[k])+1 ) //当前点的最大滑雪长度小于等于周围某点

ppt[i][j]=dfs(i+x[k],j+y[k])+1; //更改当前点的最大滑雪长度

return ppt[i][j];

}

int main()

{

int max=0,i,j;

std::cin>>r>>c;

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

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

{

std::cin>>node[i][j];

ppt[i][j]=0; //初始化为0

}

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

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

if(max<dfs(i,j))

max=dfs(i,j);

std::cout<<max + 1<<std::endl;

system("pause");

return 0;

}

本题的另一种解法如下，使用的不是记忆化搜索：

#include <iostream>

#include <algorithm>

const int MAX = 101;

struct Point

{

int x; //横坐标

int y; //纵坐标

}point[MAX*MAX]; //存储输入数组中每个点的坐标信息

int height[MAX][MAX]; //存储每个点的高度,即输入的坐标值

int ans[MAX][MAX]; //dp数组，记录每一个点的最大滑雪长度

//按Point中D的h从低到高排序

bool cmp(const Point& a, const Point& b)

{

return height[a.x][a.y] < height[b.x][b.y];

}

int main()

{

int R, C;

int flag = 0;

memset(ans, 0, sizeof(ans)); //初始化

std::cin>>R>>C;

for(int i=0; i<R; i++)

{

for(int j=0; j<C; j++)

{

std::cin>>height[i][j];

point[flag].x = i;

point[flag].y = j;

flag++;

}

}

//对point数组按高度进行排序

std::sort(point, point+R*C, cmp);

int X0, Y0, tmp;

int maxLen = 0;

for(int i=0; i<R*C; i++)//按高度从低到高扫描

{

X0 = point[i].x;

Y0 = point[i].y;

//右边的点比当前点高,并且右边点的最长下降子序列小于等于当前点

//则说明右边点的最长子序列可以再加1,从而高度降到当前点,同时丢弃右边点

//原有的较短的下降子序列，改为当前点下降序列长+1

tmp = Y0 + 1;

if(tmp<C && height[X0][Y0] < height[X0][tmp] &&

ans[X0][Y0] >= ans[X0][tmp])

{

ans[X0][tmp] = ans[X0][Y0] + 1;

}

//左边的点比当前点高,并且左边点的最长下降子序列小于等于当前点

//则说明左边点的最长子序列可以再加1,从而高度降到当前点,同时丢弃左边点

//原有的较短的下降子序列，改为当前点下降序列长+1

tmp = Y0 - 1;

if(tmp>=0 && height[X0][Y0] < height[X0][tmp] &&

ans[X0][Y0] >= ans[X0][tmp])

{

ans[X0][tmp] = ans[X0][Y0] + 1;

}

//上边的点比当前点高,并且上边点的最长下降子序列小于等于当前点

//则说明上边点的最长子序列可以再加1,从而高度降到当前点,同时丢弃上边点

//原有的较短的下降子序列，改为当前点下降序列长+1

tmp = X0 + 1;

if(tmp<R && height[X0][Y0] < height[tmp][Y0] &&

ans[X0][Y0] >= ans[tmp][Y0])

{

ans[tmp][Y0] = ans[X0][Y0] + 1;

}

//下边的点比当前点高,并且下边点的最长下降子序列小于等于当前点

//则说明下边点的最长子序列可以再加1,从而高度降到当前点,同时丢弃下边点

//原有的较短的下降子序列，改为当前点下降序列长+1

tmp = X0 - 1;

if(tmp>=0 && height[X0][Y0] < height[tmp][Y0] &&

ans[X0][Y0] >= ans[tmp][Y0])

{

ans[tmp][Y0] = ans[X0][Y0] + 1;

}

}

for(int i=0; i<R; i++)

{

for(int j=0; j<C; j++)

{

if(ans[i][j] > maxLen)

{

maxLen = ans[i][j];

}

}

}

std::cout<<maxLen + 1<<std::endl; //ans[?]初始值是0,故计算长度是加1

system("pause");

return 0;

}

上面这段代码有一个简化的版本，不过思维方式是相反的：

#include <iostream>

#include <algorithm>

const int N = 101;

int h[N][N], ans[N][N];

int x, y, n, m, x0, y0;

struct point {

int i, j;

} a[N*N];

bool cmp(const point a, const point b) {

return h[a.i][a.j] < h[b.i][b.j];

}

int main() {

while (std::cin>>n>>m) {

if (!n && !m)

return 0;

int t = 0;

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

for (int j = 1; j <= m; ++j, ++t) {

std::cin>>h[i][j];

a[t].i = i;

a[t].j = j;

}

memset(ans, 0, sizeof (ans)); //初始化

std::sort(a, a + t, cmp); //从小到大排序

int maxn = 0;

for (int i = 0; i < t; ++i) {

x0 = a[i].i;

y0 = a[i].j;

x = x0 + 1;//右边点

if ( x <= n && h[x][y0] < h[x0][y0] && ans[x][y0] >= ans[x0][y0])

ans[x0][y0] = ans[x][y0] + 1;

x = x0 - 1;//左边点

if (x > 0 && h[x][y0] < h[x0][y0] && ans[x][y0] >= ans[x0][y0])

ans[x0][y0] = ans[x][y0] + 1;

y = y0 + 1;//下边点

if ( y <= m && h[x0][y] < h[x0][y0] && ans[x0][y] >= ans[x0][y0])

ans[x0][y0] = ans[x0][y] + 1;

y = y0 - 1;//上边点

if (y > 0 && h[x0][y] < h[x0][y0] && ans[x0][y] >= ans[x0][y0])

ans[x0][y0] = ans[x0][y] + 1;

if (ans[x0][y0] > maxn)

maxn = ans[x0][y0];

}

std::cout<<maxn + 1<<std::endl; //结果算的是滑过的点数

}

system("pause");

return 0;

}