C++11(clang++ 3.9) 解法, 执行用时: 38ms, 内存消耗: 6744K, 提交时间: 2020-08-07 18:12:58

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
vector<vector<int>> g;
int n, m, k;
struct point {
    int x, y, h;
    bool operator<(const point& b) const { return h < b.h; }
};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    g.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        g[i].resize(m + 1);
        for (auto& x : g[i]) x = inf;
    }
    priority_queue<point> q;
    for (int i = 0, x, y, h; i < k; i++) {
        cin >> x >> y >> h;
        g[x][y] = h;
        q.push({x, y, h});
    }
    if (k == 0) q.push({1, 1, 0});
    point now;
    while (!q.empty()) {
        now = q.top();
        q.pop();
        int x = now.x, y = now.y, h = now.h;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
            if (g[nx][ny] == inf) {
                g[nx][ny] = h - 1;
                q.push({nx, ny, h - 1});
            }
            else if (abs(g[nx][ny] - h) > 1) {
                cout << "No\n";
                return 0;
            }
        }
    }
    cout << "Yes\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << g[i][j] << ' ';
        cout << '\n';
    }
}

C++14(g++5.4) 解法, 执行用时: 49ms, 内存消耗: 6412K, 提交时间: 2020-08-05 22:46:14

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e5+5,inf=1e9,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
typedef pair<int,int> pii;
vector<vector<int>> a;
priority_queue<pair<int,pair<int,int>>> q;
int main(){
    int i,n,m,k;
    int x,y,h;
    int flg=-1;
    scanf("%d%d",&n,&m);
    a.resize(n);
    for (auto &v:a){
        v.resize(m);
        for (auto &h:v)
            h=-inf;
    }
    scanf("%d",&k);
    for (i=0;i<k;i++){
        scanf("%d%d%d",&x,&y,&h);
        a[x-1][y-1]=h;
        q.push(make_pair(h,make_pair(x-1,y-1)));
    }
    if (q.empty()){
        a[0][0]=0;
        q.push(make_pair(0,make_pair(0,0)));
    }
    while (q.size()){
        auto t=q.top(); q.pop();
        int h=t.first,x=t.second.first,y=t.second.second;
        for (int d=0;d<4;d++) if (x+dx[d]>=0&&x+dx[d]<n&&y+dy[d]>=0&&y+dy[d]<m){
            if (a[x+dx[d]][y+dy[d]]==-inf){
                a[x+dx[d]][y+dy[d]]=h-1;
                q.push(make_pair(h-1,make_pair(x+dx[d],y+dy[d])));
            }
            else if (abs(a[x+dx[d]][y+dy[d]]-h)>1){
                puts("No"); return 0;
            }
        }
    }
    puts("Yes");
    for (int i=0;i<n;i++) for (int j=0;j<m;j++) printf("%d%c",a[i][j],j<m-1?' ':'\n');
    return 0;
}