样例未过求调
查看原帖
样例未过求调
1179906
hhy8399楼主2024/12/15 20:51
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 2e3 + 10;

struct node {
	int x,y,score;
	bool operator < (const node& a) const{
		return a.score < score;
	}
};

int h,w,x,p,q,ans;
int a[MAXN][MAXN];
int fx[] = {1,-1,0,0},fy[] = {0,0,1,-1};
bool mp[MAXN][MAXN];

void bfs() {
	priority_queue <node> que;
	node k;
	k.x = p,k.y = q,k.score = a[p][q];
	for(int i = 0;i < 4;i++) {
		int hx = k.x + fx[i],hy = k.y + fy[i];
		if(hx > 0 && hy > 0 && hx <= h && hy <= w && !mp[hx][hy]) {
	//		cout << "Yes" << i << "\n";
			mp[hx][hy] = true;
			node z;
			z.x = hx,z.y = hy,z.score = a[hx][hy];
			que.push(z);
		}
	}
	while(que.size()) {
		k = que.top();
		que.pop();
		int y;
		if(ans % x == 0) {
			y = ans / x;
		}
		else {
			y = ans / x + 1;
		}
		if(y <= k.score) {
			continue;
		}
	//	cout << "Yes1\n";
		ans += k.score;
		for(int i = 0;i < 4;i++) {
			int hx = k.x + fx[i],hy = k.y + fy[i];
			if(hx > 0 && hy > 0 && hx <= h && hy <= w && !mp[hx][hy]) {
		//		cout << "Yes" << i << "\n";
				mp[hx][hy] = true;
				node z;
				z.x = hx,z.y = hy,z.score = a[hx][hy];
				que.push(z);
			}
		}
	}
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> h >> w >> x >> p >> q;
	for(int i = 1;i <= h;i++) {
		for(int j = 1;j <= w;j++) {
			cin >> a[i][j];
		}
	}
	ans = a[p][q];
	memset(mp,false,sizeof mp);
	bfs();
	cout << ans << "\n";
	return 0;
}
2024/12/15 20:51
加载中...