优先队列的为什么过不了QAQ
查看原帖
优先队列的为什么过不了QAQ
765192
heiheiwolala楼主2023/11/7 17:29

参考了解答区的一位使用优先队列的,为什么我的总是过不了?QAQ

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 200;
int Height[N][N], maxHigh[N][N];
struct Item {
	int val;
	pair<int, int> indices;
	Item(int v, int i, int j) : val(v), indices(make_pair(i, j)) {}
};
struct Compare {
	bool operator()(const Item &a, const Item &b) {
		return a.val > b.val;
	}
};
void solve() {
	int n, m;
	cin >> n >> m;
	memset(maxHigh, 0, sizeof(maxHigh));
	memset(Height, 0, sizeof(Height));
	priority_queue<Item, vector<Item>, Compare> pq;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> Height[i][j];
			pq.push(Item(Height[i][j], i, j));
		}
	}
	int res = 1;
	while (!pq.empty()) {
		Item item = pq.top();
		int val = item.val, i = item.indices.first, j = item.indices.second;
		if (val > Height[i - 1][j]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i - 1][j] + 1);
		if (val > Height[i][j + 1]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i][j + 1] + 1);
		if (val > Height[i + 1][j]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i + 1][j] + 1);
		if (val > Height[i][j - 1]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i][j - 1] + 1);
		res = max(res, maxHigh[i][j]);
		pq.pop();
		//cout << res << "(" << i << "," << j << ") " << val << endl;
	}
	cout << res << "\n";
	return;
}
int main() {
	int _ = 1;
	while (_--) solve();
	return 0;
}
2023/11/7 17:29
加载中...