当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6749：Mosquito

题目描述
房间是个 $n*m$ 的网格，一共有 $k$ 个窗户，都在上下左右四条边上。在第 0 时刻，每个窗户对应的格子上都会出现若干只蚊子。

蚊子每个时刻可以往上下左右移动一格或者呆在原地不动。

假设这些蚊子都足够聪明，请问最少花费多少时刻，使得所有格子上都有至少一只蚊子？

蚊子在第 0 时刻不能动。
输入解释
第一行一个正整数 $test(1 \le test \le 10)$ 表示数据组数。

对于每组数据，第一行三个整数 $n, m, k(1 \le n, m \le 1000, 1 \le k \le 6)$ 表示房间的大小和窗户的个数。

接下来 $k$ 行，每行三个整数 $x, y, z(1 \le z \le nm)$ 表示窗户的坐标以及出现在这个窗户的初始蚊子的数目。

横坐标从 $1...n$ 编号，纵坐标从 $1...m$ 编号，数据保证窗户一定在边界上。
输出解释
对于每组数据，一行一个整数表示答案。如果无解，输出 -1。
输入样例 
2
5 5 4
1 1 10
1 5 10
5 1 10
5 5 10
3 3 1
1 1 8
输出样例 
4
-1
来自杭电HDUOJ的附加信息
Recommend liuyiding
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2020 年百度之星·程序设计大赛 - 初赛一
源链接： HDU-6749
最后修改于 2020-10-25T23:34:01+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
20000/10000MS(Java/Others) 131072/131072K(Java/Others)