呜呜呜dalao路过给蒟蒻看一下(90pts,第二个点居然MLE了)
查看原帖
呜呜呜dalao路过给蒟蒻看一下(90pts,第二个点居然MLE了)
393190
aldol_reaction楼主2020/11/22 21:25

我开的数组也不大啊QAQ真的要疯了求救求救

#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;
}














	return 0;
}
2020/11/22 21:25
加载中...