关于优先队列做法中max两种写法的区别疑问
查看原帖
关于优先队列做法中max两种写法的区别疑问
1125645
DyingEncoder楼主2025/1/21 21:11

下面代码中有两处用 //* 标注了出来:

用//*1的代码仅有80pts,但是用//2*则有100pts,求原因?

#include <bits/stdc++.h>
using namespace std;
int _map[105][105];
int lev[105][105];//某点离它所在滑坡的峰顶的距离
int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};//四个方向滑雪
int R, C;
struct H {//每个滑坡上的点的高度、位置
	int height;
	int r, c;
	H(int _h, int _r, int _c) {
		height = _h;
		r = _r;
		c = _c;
		lev[r][c] = 1;
	}
};
struct cmp {
	bool operator() (H h1, H h2) {
		return h1.height < h2.height;
	}
};
priority_queue<H, vector<H>, cmp> Q;//优先队列,优先从最高的点开始往下走
int ans = -100;
int main() {
	std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> _map[i][j];
			Q.push(H(_map[i][j], i, j));//存入每个点
		}
	}
	while (!Q.empty()) {
		int i = Q.top().r, j = Q.top().c;
		for (int t = 0; t < 4; t++) {
			int ni = i + d[t][0], nj = j + d[t][1];
			if (1 <= ni && ni <= R && 1 <= nj && nj <= C && _map[ni][nj] < _map[i][j]) {
				lev[ni][nj] = max(lev[ni][nj], lev[i][j] + 1);
				//1*:ans=max(ans,lev[ni][nj]);
			}
		}
		Q.pop();
	}
	//2*
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			ans=max(ans,lev[i][j]);
		}
	}
	//*
	cout << ans;
	return 0;
}
2025/1/21 21:11
加载中...