谁能找出其中的BUG，立即给100分
题目：
描述
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
下面是我的解。在自己电脑上通过了，可惜提交时总是报WrongAnswer错误！！！提示是：输出结果不对，看看是不是忘了输出必要的换行或者大小写错误？如果不是，那很可能你的程序逻辑有问题，或者有特殊的数据没有考虑。
- C/C++ code
#include <stdio.h>int r,c,sum=0,max=0;//全局变量，r:行，c:列 sum:临时路径长度 max:最终路径长度int comp(int h[100][100],int i,int j){ int tmp; if( ((tmp=i-1)>=0) && (h[tmp][j]<h[i][j]) ) //上 { sum++; comp(h,tmp,j); } if( ((tmp=i+1)<r) && (h[tmp][j] < h[i][j]))//下 { sum++; comp(h,tmp,j); } if( ((tmp=j-1)>=0) && (h[i][tmp] < h[i][j]))//左 { sum++; comp(h,i,tmp); } if( ((tmp=j+1)<c) && (h[i][tmp] < h[i][j]))//右 { sum++; comp(h,i,tmp); } if(sum >max) max=sum; sum--; return max;}int main(){ int n; //n组测试数据 int high[10][100][100];//用于保存N组测试数据 int high_tmp[100][100];//用于临时保存测试数据 int i,j,k; int res,maxpath;//保存最长区域长度 scanf("%d",&n); for(k=0;k<n;k++) //输入数据 { scanf("%d %d",&r,&c); if( (r<1 || r >100) || (c < 1 || c > 100) ) //判断输入合法性 return 0; for(i=0;i<r;i++) for(j=0;j<c;j++) scanf("%d",&high[k][i][j]); } for(k=0;k<n;k++) { maxpath=0; for(i=0;i<r;i++) //分别将每组数据保存进临时数组 for(j=0;j<c;j++) { high_tmp[i][j]=high[k][i][j]; if(high_tmp[i][j]<0 || high_tmp[i][j]>10000) return 0; } for(i=0;i<r;i++) //找出最长区域长度 for(j=0;j<c;j++) { sum=max=0; res=comp(high_tmp,i,j); //递归函数 if(res > maxpath) maxpath=res; } printf("%d\n",maxpath+1); } return 1;}欢迎大家踊跃参与
[解决办法]
看了一下题。就是一个dfs+剪枝。lz写的程序那么长，测试数据痛过了。通过的是几组样例，是上面一组吗？
不如把oj链接发来，如果大家AC了，再回头测试你的数据啊。如果本身是程序错，那么长的程序看完了岂不是很纠结？
还有啊，【输出结果不对，看看是不是忘了输出必要的换行或者大小写错误】这种错误是pe不是wa。
[解决办法]
每组数据的r和c都不一样，但你永远用的是最后一组数据的r和c
[解决办法]
- C/C++ code
#include <iostream>using namespace std;const int maxsize=100, inf=~0U>>1, dir[4][2]={ {-1,0}, {0,1}, {1,0}, {0,-1} };//directionint ans,n,r,c,graph[maxsize+1][maxsize+1],path[maxsize+1][maxsize+1];//path[][] is memoize.bool Can(int x,int y){ return (x>=1 && x<=r && y>=1 && y<=c);}int find(int x,int y){ if(path[x][y]!=-1)return path[x][y];//get memory int nx,ny; for(int i=0;i<4;i++){ nx=x+dir[i][0];ny=y+dir[i][1]; if(Can(nx,ny) && graph[nx][ny]<graph[x][y]) path[x][y]=max(path[x][y],find(nx,ny)+1);//memorize } if(path[x][y]==-1){ path[x][y]=1; return 1; }//path[x][y]=1 if and only if node(x,y) has no way outside. else return path[x][y];}int main(){ for(cin>>n;n!=0;n--){ cin>>r>>c; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++){ cin>>graph[i][j]; path[i][j]=-1; } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++){ find(i,j); ans=max(ans,path[i][j]); } cout<<ans<<endl; } //system("pause"); return 0;}
[解决办法]
lz我说把链接贴出来会有人帮你的嘛。嘎嘎
[解决办法]
这道题好像写过，典型的dp问题啊，建议楼主用dp来做吧
[解决办法]
楼主我的通过了你应该能看到。我用java写的第一次把包导进去了编译出错。o(□)o。
看时间是限制3000MS，代码就没有优化。
- Java code
import java.util.*;public class Main { static int max,sum; static int h[][]=new int[1002][1002]; //static int a[][]=new int[1002][1002];//这个打算打表优化的，AC了就没用上。 static void dfs(int h[][],int i,int j) { if(h[i][j]<h[i+1][j]&&h[i][j]<h[i][j-1]&&h[i][j]<h[i-1][j]&&h[i][j]<h[i][j+1]) { max=max<sum?sum:max; } else { for(int k=0;k<4;k++) { switch(k) { case 0:if(h[i][j]>h[i][j+1]) {sum++;dfs(h,i,j+1);sum--;};break; case 1:if(h[i][j]>h[i+1][j]) {sum++;dfs(h,i+1,j);sum--;};break; case 2:if(h[i][j]>h[i][j-1]) {sum++;dfs(h,i,j-1);sum--;};break; case 3:if(h[i][j]>h[i-1][j]) {sum++;dfs(h,i-1,j);sum--;};break; } } } } public static void main(String args[]) { Scanner cin=new Scanner(System.in); int n=cin.nextInt(); while(n!=0) { max=1;n--; int r=cin.nextInt(); int c=cin.nextInt(); for(int i=0;i<=r+1;i++) h[i][0]=h[i][c+1]=32767; for(int j=1;j<=c;j++) h[0][j]=h[r+1][j]=32767; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) h[i][j]=cin.nextInt(); for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) { sum=1; dfs(h,i,j); } } System.out.printf("%d\n",max); } }}
[解决办法]
- C/C++ code
int comp(int h[100][100],int i,int j){ int tmp; if( ((tmp=i-1)>=0) && (h[tmp][j]<h[i][j]) ) //上 { sum++; comp(h,tmp,j); sum--;//写在这里 } if( ((tmp=i+1)<r) && (h[tmp][j] < h[i][j]))//下 { sum++; comp(h,tmp,j); sum--;//写在这里 } if( ((tmp=j-1)>=0) && (h[i][tmp] < h[i][j]))//左 { sum++; comp(h,i,tmp); sum--;//写在这里 } if( ((tmp=j+1)<c) && (h[i][tmp] < h[i][j]))//右 { sum++; comp(h,i,tmp); sum--;//写在这里 } if(sum >max) max=sum; //sum--;//这个地方有问题。如果上面四个if都不成立sum--就错了应该写在里面。 return max;}
[解决办法]
lz成功了加分呀 好一阵忙活 lz好运哈
[解决办法]