第二个点RE,求助

P1434 [SHOI2002] 滑雪

wzhhhhh @ 2018-03-29 19:13:27

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 111;

struct point {
    int h, x, y;
}p[maxn * maxn];

int r, c, cnt, ans;
int map[maxn][maxn], maxh[maxn][maxn];

bool cmp(point a,point b)
{
    return a.h > b.h;
}

void dfs(int cr, int cc,int cur)
{
    if(cur < maxh[cr][cc]) return ;
    else maxh[cr][cc] = cur;
    if(cr > 0 && map[cr][cc] > map[cr - 1][cc]) {
        dfs(cr - 1, cc, cur + 1);
        maxh[cr - 1][cc] = cur + 1;
    }
    if(cr < r - 1 && map[cr][cc] > map[cr + 1][cc]) {
        dfs(cr + 1, cc, cur + 1);
        maxh[cr + 1][cc] = cur + 1;
    }
    if(cc > 0 && map[cr][cc] > map[cr][cc - 1]) {
        dfs(cr, cc - 1, cur + 1);
        maxh[cr][cc - 1] = cur + 1;
    }
    if(cc < c - 1 && map[cr][cc] > map[cr][cc + 1]) {
        dfs(cr, cc + 1, cur + 1);
        maxh[cr][cc + 1] = cur + 1;
    }
    ans = max(ans, cur);
}

void scan()
{
    cin >> r >> c;
    for(int i = 0;i < r;i++) {
        for(int j = 0; j < c;j++) {
            cin >> map[i][j];
            p[cnt].h = map[i][j];
            p[cnt].x = i;
            p[cnt].y = j; 
            cnt++;
        }
    }
    sort(p, p + cnt, cmp);
}

int main()
{
    scan();
    for(int i = 0;i < r * c;i++)
    {
        if(r * c - maxh[p[i].x][p[i].y] - 1 > ans)
        dfs(p[i].x, p[i].y, 0);
    }
    cout << ans + 1 << endl;
    return 0;
}

自己认真检查后能确定不是数组越界背锅。。 手写了两组100 * 100 的数据,一组是全都是10以内的,能过,一组是从1到10000的,就跑了半天没有响应了。

求大神帮忙。。。前前后后已经折腾了两天了。。。


by Ch4rc0al @ 2018-04-08 14:31:01

我也一样,第二组RE


by 山雨木子 @ 2018-06-16 17:32:49

爆栈?


by Dickk @ 2018-09-22 14:31:06

我用bfs90分,就第二组RE。。。


|