C++14(g++5.4) 解法, 执行用时: 560ms, 内存消耗: 9708K, 提交时间: 2020-06-07 15:14:14

#include <bits/stdc++.h>
using namespace std;
int dx[] = {0,1,0,-1,0};
int dy[] = {0,0,1,0,-1};
const int N = 1010;
int p[N][N];
long long a[N][N];
struct Node
{
	int x, y;
	long long v;
	Node(int xx,int yy,long long vv)
	{
      x = xx;
	  y = yy;
	  v = vv;
	}
};
bool operator>(Node a, Node b)
{
	return a.v > b.v;
}
struct indoor
{
	/* data */
	int x,y;

}in[1010];

int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	for (;T--;)
	{
		int inum = 0;
		long long w, d, k, n, m;
         cin >> w >> d >> k;
		 cin >> n >> m;
		 for (int i = 1; i <= n; i++)
		  for (int j = 1; j <= m; j++)
		  {
			  cin >> a[i][j];
			  p[i][j] = 0;
			  if (!a[i][j]) { in[++inum].x = i;in[inum].y = j;p[i][j] = 1;} 
		  }
		priority_queue<Node,vector<Node>,greater<Node> > q;
		for (int i = 1; i <= inum; i++) q.push(Node(in[i].x,in[i].y,0)); 
		long long now = w * d;
		long long ans = 0;
		for (;!q.empty();)
		{
			int x = q.top().x;
			int y = q.top().y;
			int v = q.top().v;
			q.pop();
			if (now/d <= v) 
			{
				ans = -1;
				break;
			}
			else now += v;
			for (int i = 1; i <= 4; i++)
			{
				int nx = x+dx[i];
				int ny = y+dy[i];
				if (nx > 0 && ny > 0 && nx <= n && ny <= m && !p[nx][ny])
				{
					p[nx][ny] = 1;
					q.push(Node(nx, ny, a[nx][ny]));
				}
			}
		}
		if (ans != -1) 
		{
			cout << "YES" << endl;
			cout << now/d-w << endl;
		}
		else cout << "NO" << endl;
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 786ms, 内存消耗: 5980K, 提交时间: 2020-06-08 17:00:32

#include<bits/stdc++.h>
using namespace std;

typedef struct{
	int x, y;
	long long value;
}Moster;

bool operator<(Moster a,Moster b){
	return a.value>b.value;
}

long long maps[505][505];
bool maps1[505][505];
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		priority_queue<Moster> que;
		memset(maps1,true,sizeof(maps1));
		long long n, m, w, d, k;
		scanf("%lld%lld%lld%lld%lld",&w,&d,&k,&n,&m);
		for(int i = 0;i < n;i++){
		 	for(int j = 0;j < m;j++){
		 		scanf("%lld",&maps[i][j]);
		 		if(maps[i][j]==0){
					Moster M;
					maps1[i][j]=false;
					M.x=i;M.y=j;M.value=0; 
		 			que.push(M);
				}
			}
		}
		long long EXP = 0;
		while(!que.empty()&&w+EXP/d>que.top().value){
			Moster M = que.top();que.pop();
			EXP+=M.value;
			int x = M.x, y = M.y;
			for(int i = 0;i < 4;i++){
				int nx = x + dx[i], ny = y + dy[i];
				if(nx>=0&&ny>=0&&nx<n&&ny<m&&maps1[nx][ny]){
					maps1[nx][ny]=false;
					M.x=nx;M.y=ny;M.value=maps[nx][ny]; 
					que.push(M);
				}
			}
		}
		if(que.empty()) printf("YES\n%lld\n",EXP/d);
		else printf("NO\n"); 
		while(!que.empty()) que.pop();
	}
	return 0;
}