IsQian @ 2023-11-07 17:29:55
参考了解答区的一位使用优先队列的,为什么我的总是过不了?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;
}
by KinoTsuki @ 2024-01-03 22:32:28
@heiheiwolala
应该由海拔从低到高枚举
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 = 0;
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+1 << "\n";
return;
}
这样就能过了 OAO