31 Jul 2012

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;
}

No comments :

Post a Comment