Question

这是北大acm_1088题 我写了个代码 那个代码里的递归错了，但我不知道错在哪里，请高人指点下

这是北大acm_1088题 我写了个代码 测试的结果很奇怪，应该是那个代码里的递归错了，我打理了下思路，但实在不知道错在哪里，请高人指点下...谢谢
#include<stdio.h>
int C, R, a[103][103];//1~100
int f(int h, int i, int j)
{
int m = -999;
if(a[i-1][j]<h || a[i][j+1]<h || a[i+1][j]<h || a[i][j-1]<h)
{
if(f(a[i-1][j], i-1, j)>m && a[i-1][j]<h)
m = f(a[i-1][j], i-1, j) + 1;
if(f(a[i][j+1], i, j+1)>m && a[i][j+1]<h)
m = f(a[i][j+1], i, j+1) + 1;
if(f(a[i+1][j], i+1, j)>m && a[i+1][j]<h)
m = f(a[i+1][j], i+1, j) + 1;
if(f(a[i][j-1], i, j-1)>m && a[i][j-1]<h)
m = f(a[i][j-1], i, j-1) + 1;

if(a[i-1][j]<h)
m = f(a[i-1][j], i-1, j) + 1;
if(a[i][j+1]<h)
return m;
}
else
return 1;
}
int main()
{
int i, j, x, y, max = 0, l;
scanf("%d%d", &C, &R);
for(i=1; i<=C; i++)
for(j=1; j<=R; j++)
scanf("%d", &a[i][j]);//h<10000
for(j=0; j<R+1; j++)
a[0][j] = 9999999;
for(i=0; i<C+1; i++)
a[i][R+1] = 9999999;
for(j=R+1; j>0; j--)
a[C+1][j] = 9999999;
for(i=R+1; i>0; i--)
a[i][0] = 9999999;
for(i=1; i<=C; i++)
{
for(j=1; j<=R; j++)
{
if(a[i][j] > max)
{
max = a[i][j];
x = i;
y = j;
}
}
}

l = f(a[x][y], x, y);
printf("%d", l);
//printf("%d\n", a[x][y]);
return 0;
}
听各位的指导 我改进了下，现在能输出正确结果，可不知道为什么始终是WA...请高手再指点指点 谢谢..代码如下
#include<stdio.h>
int C, R, a[100][100], cnt[100][100];
int f(int h, int i, int j)
{
int m = 0;
if(cnt[i][j] > 0) return cnt[i][j];
if(a[i-1][j]<h && i-1>=0)
if(f(a[i-1][j], i-1, j)>m)
m = f(a[i-1][j], i-1, j);
if(a[i][j+1]<h && j+1<R)
if(f(a[i][j+1], i, j+1)>m)
m = f(a[i][j+1], i, j+1);
if(a[i+1][j]<h && i+1<C)
if(f(a[i+1][j], i+1, j)>m)
m = f(a[i+1][j], i+1, j);
if(a[i][j-1]<h && j-1>=0)
if(f(a[i][j-1], i, j-1)>m)
m = f(a[i][j-1], i, j-1);
return cnt[i][j] = m + 1;

}
int main()
{
int i, j, x, y, max = 0;
scanf("%d%d", &C, &R);
for(i=0; i<C; i++)
for(j=0; j<R; j++)
{
scanf("%d", &a[i][j]);
cnt[i][j] = 0;
}

for(i=0; i<C; i++)
{
for(j=0; j<R; j++)
{
if(a[i][j] > max)
{
max = a[i][j];
x = i;
y = j;
}
}
}

printf("%d\n", f(a[x][y], x, y));
return 0;
}

Answer 1

看到你新写的代码了.

对于这个题目, 要把每个点作为起点枚举一遍, 看哪个点作为起点能获得最大高度. 并不是从最高的那个点滑下来, 距离就一定最长. 很容易举出例子来, 稍微想下就清楚了.

good luck.

------------------------------------ 以下是原回答-------------------------------------------
1楼说的没错, 纯递归是过不了的, 需要动态规划, 即是保存每个点计算结果, 如果某个点已经计算过, 则不再重复计算, 而是直接取结果值.

写了份代码, 已经ac的. 有详细注释. 如有地方没解释明白, 可以再问我.

/*
1. f(i, j)表示从点(i,j)出发, 所能滑行的最大长度
2. f(i, j) = Max( f(能到达的相邻节点) + 1 );
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;

const int NUL = -1;
const int MAXN = 103;
const int d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
int ni, nj;
int mp[MAXN][MAXN], dp[MAXN][MAXN];

int f(int x, int y)
{
if (dp[x][y] != NUL) return dp[x][y]; // 如果当前点已经被计算过, 直接返回结果

int result = 1, xx, yy; // result保存f(x,y)的值.
for (int di=0; di<4; di++)
{
xx = x + d[di][0], yy = y + d[di][1]; // 根据方向数组, 计算出当前方向对应的坐标
if (xx<0 || yy<0 || xx>=ni || yy>=nj) continue; // 如果坐标越界, 跳过
if (mp[xx][yy] >= mp[x][y]) continue; // 如果目标高度大于当前高度, 跳过
result = max(result, f(xx, yy) + 1); // 更新能滑行距离的最大值
}
// 如果当前点xy是最低点, 则四次循环中result都没有被改变, 则result等于初值1. 正好符合结果

return dp[x][y] = result; // 保存结果值, 并返回
}

int main()
{
int i, j, result = 0;
scanf("%d%d", ∋, &nj);
for (i=0; i<ni; i++)
for (j=0; j<nj; j++)
scanf("%d", &mp[i][j]), dp[i][j] = NUL;

for (i=0; i<ni; i++)
for (j=0; j<nj; j++)
result = max(result, f(i, j));

printf("%d", result);
}

Answer 2

RE一般是由于数组访问越界或者递归有问题
这题你是用递归做的, 时间复杂度太大...必须用动态规划才行的通

碰巧我做过一道类似的题, 只不过那题中的数组是正方形的, 所以输入有些不同,
题目链接:

我的代码: c++编译运行通过
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

const int MAX = 103;
const int NUL = -1;
const int ERR = -2;
int a[MAX][MAX];
int stat[MAX][MAX];
int n;

bool check(int i, int j)
{
if (i<0 || j<0 || i>n-1 || j>n-1)
return false;
else
return true;
}

int f(int ii, int jj)
{
if (ii<0 || jj<0 || ii>n-1 || jj>n-1)
return ERR;

if (stat[ii][jj] != NUL)
return stat[ii][jj];

int i, j, k=0, round[10], max=0;

for (i=-1; i<2; i++)
{
for (j=-1; j<2; j++)
{
if (i==0 || j==0)
{
if (i==0 && j==0)
continue;
if (check(ii+i, jj+j) == false)
round[k] = 0;
else
{
if (a[ii+i][jj+j] >= a[ii][jj])
round[k] = 0;
else
round[k] = f(ii+i, jj+j);
}
k++;
}
}
}

for (i=0; i<4; i++)
if (max < round[i])
max = round[i];

stat[ii][jj] = max + 1;
return stat[ii][jj];
}

int main()
{
//input
int total;
scanf("%d", &total);

//circle
while (total--)
{
int i, j, max=0;
scanf("%d", &n);
for (i=0; i<n; i++)
for (j=0; j<n; j++)
scanf("%d", &a[i][j]), stat[i][j] = NUL;

for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
int t = f(i, j);
if (max < t)
max = t;
}

printf("%d\n", max);
}

return 0;
}