题解

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
#include <algorithm>
#pragma GCC optimize(2)
#define int long long
using namespace std;
struct node{
    int x, y, step;
    bool operator < (const node &b) const{
		return step < b.step;
	}
}a[1005];
vector <node> v;
int n, m, k, x, y, t;
signed dis[5005][5005];
bool vis[5005][5005];
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};
bool check(int x, int y){
	if(x < 1 || x > n) return 0;
	if(y < 1 || y > m) return 0;
	if(vis[x][y]) return 0;
	return 1;
}
void bfs(){
	queue <node> q;
	q.push(a[1]);
	dis[a[1].x][a[1].y] = a[1].step, vis[a[1].x][a[1].y] = 1;
	int ct = 2;
	while(!q.empty()){
		node head = q.front();
		q.pop();
		while(ct <= k && a[ct].step <= head.step){
			if(!vis[a[ct].x][a[ct].y]){
				dis[a[ct].x][a[ct].y] = a[ct].step, vis[a[ct].x][a[ct].y] = 1;
				q.push(a[ct]);
			}
			ct++;
		}
		for(int i = 0; i < 4; i++){
			int xx = head.x + dir[i][0], yy = head.y + dir[i][1];
			if(check(xx, yy)){
				vis[xx][yy] = 1, dis[xx][yy] = head.step + 1;
				q.push({xx, yy, head.step + 1});
			}
		}
	}
}
const int mod = 998244353;
signed main(){
	memset(dis, 63, sizeof(dis));
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i++){
        cin >> a[i].x >> a[i].y >> a[i].step;
        dis[x][y] = t;
    }
    sort(a + 1, a + k + 1);
    bfs();
    int ct = 0, pow = 1;
    for(int i = 1; i <= m; i++){
    	pow = pow * 233 % mod;
	}
    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= m; j++){ 
    		pow = pow * 233 % mod;
    		ct = (ct + pow * dis[i][j] % mod) % mod;
		}
	}
	cout << ct % mod;
    
    return 0;
}