问题描述

在一个 N 行 M 列的棋盘上，摆放着 K 个士兵。一个士兵占据一个格子（可能有多个士兵占据同一个格子）。

第 i 个士兵控制棋盘上所有与它相距不超过 Ri 的格子。

两个格子 (X1, Y1)、(X2, Y2) 间的距离定义为 曼哈顿距离：
|X1 - X2| + |Y1 - Y2|

现在给出 K 个士兵的坐标，请你写一个程序返回 被控制的格子的总数（重复控制的格子只算一次）。

输入格式

• 第 1 行：三个正整数 N、M 和 K。
• 第 2 ~ K+1 行：每行三个自然数 X、Y 和 R。
  • X 表示士兵所在的行编号；
  • Y 表示士兵所在的列编号；
  • R 表示士兵的控制范围。

数据范围

在 100% 的数据中：

• 1 ≤ N, M ≤ 100000000
• 1 ≤ K ≤ 100000

输出格式

输出一个整数，表示被至少一个士兵控制的格子总数。

🧪 示例输入

3 3 2
1 1 1
3 3 1

🧪 示例输出

7

解释：第一个士兵控制 (1,1), (1,2), (2,1)；第二个士兵控制 (3,3), (3,2), (2,3)；中间 (2,2) 被两者共同控制，总计 7 个格子。

10 10 10
2 7 2
2 1 3
7 7 5
5 9 0
2 6 0
8 1 2
9 1 0
10 8 6
9 3 0
1 9 2

89

提示

没有写明提示

题目来源

By Cqf