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。。。