aldol_reaction @ 2020-11-22 23:24:04
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<set>
using namespace std;
#define maxn 105
typedef pair<pair<int, int>, int> ppii;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
int r, c, ans, a[maxn][maxn], z;
queue<ppii> q;
struct node {
int x, y, val;
} w[maxn*maxn];
bool cmp(node a, node b) {
return a.val > b.val;
}
int bfs(int x, int y) {
int ret = 1;
q.push(ppii(make_pair(x, y), 1));
while(!q.empty()) {
ppii p = q.front();
q.pop();
for(int i = 0; i < 4; ++i) {
int x = p.first.first, y = p.first.second, cnt = p.second;
int nx = x+dx[i], ny = y+dy[i];
if(0 <= nx && nx < r && 0 <= ny && ny < c && a[x][y] > a[nx][ny]) {
++cnt;
ret = max(cnt, ret);
q.push(ppii(make_pair(nx, ny), cnt));
}
}
}
return ret;
}
int main() {
cin >> r >> c;
for(int i = 0; i < r; ++i) {
for(int j = 0; j < c; ++j, ++z) {
scanf("%d", &a[i][j]);
w[z].val = a[i][j];
w[z].x = i;
w[z].y = j;
}
}
sort(w, w+r*c, cmp);
ans = bfs(w[0].x, w[0].y);
for(int i = 1; i < r*z; ++i) {
if(ans >= w[i].val) {
cout << ans;
return 0;
}
ans = max(bfs(w[i].x, w[i].y), ans);
}
cout << ans;
return 0;
}
by A_Đark_Horcrux @ 2020-11-22 23:31:36
@aldol_reaction 加一个记忆化就好了
by aldol_reaction @ 2020-11-22 23:32:39
@A_Đark_Horcrux 。。关键我就不太明白。。bfs怎么还MLE了,我也没有用递归
by A_Đark_Horcrux @ 2020-11-22 23:35:09
@aldol_reaction 队列的空间也是空间啊qwq
by aldol_reaction @ 2020-11-22 23:39:21
@A_Đark_Horcrux 我太蒟蒻了。。谢谢dalao帮助