标题:一道想用深度优先搜索的题,帮忙看下这个错误是为什么?
只看楼主
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
结帖率:92%
已结贴  问题点数:20 回复次数:15 
一道想用深度优先搜索的题,帮忙看下这个错误是为什么?
题目大意:
给出一个整形二维数组(行数为n,列数为m),可以从其中任意一点出发,向前后左右移动,但是每次只能移向元素值更大的位置,求最多能移动的步数。

代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int f(int i,int j,int **a,int **s,int n,int m){
    int n1=0,n2=0,n3=0,n4=0,max1,max2,max;
    if(s[i][j]!=-1) return s[i][j];  
    if(i+1<n && a[i][j]<a[i+1][j]) n1=f(i+1,j,a,s,n,m)+1;
    if(i-1>=0 && a[i][j]<a[i-1][j]) n2=f(i-1,j,a,s,n,m)+1;
    if(j+1<m && a[i][j]<a[i][j+1]) n3=f(i,j+1,a,s,n,m)+1;
    if(j-1>=0 && a[i][j]<a[i][j-1]) n4=f(i,j-1,a,s,n,m)+1;
    max1=(n1>n2)?n1:n2;
    max2=(n>n4)?n3:n4;
    max=(max1>max2)?max1:max2;
    s[i][j]=max;
    return s[i][j];
}

int main(void){
  int T,n,m,i,j,k,maxvalue,a[1000][1000],s[1000][1000];
  scanf("%d",&T);
  while(T--){
      scanf("%d %d",&n,&m);
      for(i=0;i<n;i++){
          for(j=0;j<m;j++){
              scanf("%d",&a[i][j]);
        }
    }
    maxvalue=0;
    memset(s,-1,sizeof(s));
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            k=f(i,j,a,s,n,m);           /*这里有错误,求大佬解释下[Error] cannot convert 'int (*)[1000]' to 'int**' for argument
                                                                  '3' to 'int f(int, int, int**, int**, int, int)' */
            if(s[i][j]>maxvalue) maxvalue=s[i][j];
        }
}
    printf("%d\n",maxvalue);
}
    return 0;
}

感觉这个程序有点繁琐,希望大佬可以顺便帮忙优化
搜索更多相关主题的帖子: 深度 错误 int scanf for 
2018-05-23 23:11
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:10 
回复 楼主 青蝶
二维数组不等价于二级指针,把函数参数int** a改成 int a[][1000]就可以了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-23 23:44
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
这种解法感觉有忽略的地方

因为没有顾及到路径覆盖的问题~

1->3->4
1->2->3->4
这样第二条路径比第一条路径移动步数要+1,但由于第二次找到3的时候3已经遍历过所以就没去更新了,所以得出来的不一定是最大值~

这样可以用图论里面的求最短路径算法,从当前结点之间的最小值开始搜~

不知道具体数据范围是多少,常规解法是o(n^2),用小顶堆可以优化到o(n*log(n)),就是1000*1000这个数据范围有没有更方便的解法~

[此贴子已经被作者于2018-5-24 00:14编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-24 00:09
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
回复 3楼 九转星河
不是很懂......大佬能再解释一下么?我是想把从每个节点能走的最大步数存入一个新数组里,之后再有情况走到这些点的时候直接加上数组元素的值就行了。
比如3->4这种情况走过以后,就把从3能完成的最大步数存起来了,再遇到2->3->4,直接得到之前存的3能完成的最大步数加1。
不知道大佬说的有些情况没考虑到是哪些?
2018-05-24 00:28
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
得分:10 
回复 4楼 青蝶
做法没问题
不过看数据规模 1000*1000
有点丧心病狂
你把语法改正了
提交能AC吗

https://zh.
2018-05-24 00:43
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 4楼 青蝶
明白了,是我理解错了~
应该是每一个位置表示的是当前能移动数据的最大值,就按你那种写法,改了语法错误后,先试试能不能AC~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-24 00:57
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
回复 6楼 九转星河
不能AC,显示答案错误。我把原来程序改了三个地方:
1.数组参数那个错误。
2.最后输出的值改成了maxvalue+1,为了和样例照应,样例应该是算了一共能走几个点,我的程序算的是能走几步。
3.两个1000*1000的数组声明成了全局变量,因为写在main函数里面开不了。
还是不能AC,附上原题,求大佬帮忙~

题目描述
一个矩阵,从任意一点出发,找到最长可以走的路有多远。由于每个位置都有一定的高度,只走高度不断上升的路径。请输出所有路径中的最大值。


输入
多组数据
第一行为数据组数T 代表有T组数据。(1<=T<=10)
每组数据第一行 输入n和m分别表示矩阵的长和宽。(1<=n、m<=1e3)
紧接着n行,每行m个整数,第i行第j个整数表示矩阵中位置(i,j)处的高度。

输出
每组数据输出一行,一个整数代表最长可以走的路。

样例输入
1
2 3
1 2 3
4 5 6
样例输出
4

[此贴子已经被作者于2018-5-24 08:08编辑过]

2018-05-24 08:05
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
得分:0 
max2赋值是不是写错
n和n4比较??

https://zh.
2018-05-24 08:12
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
得分:0 
顺便 你好早啊

https://zh.
2018-05-24 08:15
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
得分:0 
回复 8楼 lin5161678
原来是这样~过了过了,多谢大佬~
2018-05-24 08:56



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-487220-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.481541 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved