ACM 滑雪问题 wrong answer - C语言论坛

已结贴√ 问题点数：30 回复次数：19

ACM 滑雪问题 wrong answer

题目
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。输入0 0结束。

Output
输出最长区域的长度。

Sample Input
Original Transformed
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
Original Transformed
25
我的代码

程序代码：

#include<stdio.h>
int node[200][200],lenth[200][200]={0},r,c;
int len(int i,int j)
{
    int dir1=0,dir2=0,dir3=0,dir4=0,max=0;
    if(lenth[i][j]>0)
        return lenth[i][j];
    if(i>=1 && node[i-1][j]<node[i][j])
        dir1=1+len(i-1,j);
    if(i<=r-2 && node[i+1][j]<node[i][j])
        dir2=1+len(i+1,j);
    if(j>=1 && node[i][j-1]<node[i][j])
        dir3=1+len(i,j-1);
    if(j<=c-2 && node[i][j+1]<node[i][j])
        dir4=1+len(i,j+1);
    if(max<dir1)
        max=dir1;
    if(max<dir2)
        max=dir2;
    if(max<dir3)
        max=dir3;
    if(max<dir4)
        max=dir4;
    return max;
}


int main()
{
    int i,j,max=0;
    scanf("%d%d",&r,&c);
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
        scanf("%d",&node[i][j]);
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
    {
        lenth[i][j]=len(i,j);
        if(max<lenth[i][j])
            max=lenth[i][j];
    }
    printf("%d\n",max+1);
    return 0;
}

我测试没有问题
但 OJ 给的结果是wrong answer
求教哪儿有问题啊

搜索更多相关主题的帖子: 滑雪　 Michael　wrong　而且　

第 2 楼

得分:0

错误在什么地方啊？

第 4 楼

得分:0

新手路过。

这世界,有没有只有阳光的地方.

第 5 楼

得分:0

我水平不够，正在研究。我感觉这道题应该用深度优化搜索的方法把，求出最长向权树。。。。。。。。我还是回去把数据结构好好看下，不丢人了

有问题一起探讨，一起进步。

第 6 楼

得分:0

新手路过

第 7 楼

得分:15

1、根据“输入0 0结束”这句判断，这题有多组数据。但你的代码是按单组数据写的。
2、从示例的结果看，如果R、C都为1时，结果为1。而看你的函数，这时的结果是0，所以建议将max初始化为1。

先修改这两点试试。

重剑无锋，大巧不工

第 8 楼

得分:0

而且不满足无后效性，需要从低到高进行

第 9 楼

得分:0

回复 8楼 czz5242199

有点不懂啊
求详解

第 10 楼

得分:0

回复 7楼 beyondyf

程序代码：

#include<stdio.h>
int node[200][200],lenth[200][200],r,c;
int len(int i,int j)
{
    int dir1=0,dir2=0,dir3=0,dir4=0,max=0;
    if(lenth[i][j]>0)
        return lenth[i][j];
    if(i>=1 && node[i-1][j]<node[i][j])
        dir1=1+len(i-1,j);
    if(i<=r-2 && node[i+1][j]<node[i][j])
        dir2=1+len(i+1,j);
    if(j>=1 && node[i][j-1]<node[i][j])
        dir3=1+len(i,j-1);
    if(j<=c-2 && node[i][j+1]<node[i][j])
        dir4=1+len(i,j+1);
    if(max<dir1)
        max=dir1;
    if(max<dir2)
        max=dir2;
    if(max<dir3)
        max=dir3;
    if(max<dir4)
        max=dir4;
    return max;
}


int main()
{
    int i,j,max=0;
    while(scanf("%d%d",&r,&c),r||c)
    {
        max=0;
        for(i=0;i<r;i++)
            for(j=0;j<c;j++)
            {
               scanf("%d",&node[i][j]);
               lenth[i][j]=0;
            }

        for(i=0;i<r;i++)
            for(j=0;j<c;j++)
        {
            lenth[i][j]=len(i,j);
            if(max<lenth[i][j])
                max=lenth[i][j];
        }
        printf("%d\n",max+1);
    }
    return 0;
}

怎么还不可以呢

[ 本帖最后由 tyf19938 于 2013-4-15 16:29 编辑 ]