311248: CF1955H. The Most Reckless Defense
Description
You are playing a very popular Tower Defense game called "Runnerfield 2". In this game, the player sets up defensive towers that attack enemies moving from a certain starting point to the player's base.
You are given a grid of size $n \times m$, on which $k$ towers are already placed and a path is laid out through which enemies will move. The cell at the intersection of the $x$-th row and the $y$-th column is denoted as $(x, y)$.
Each second, a tower deals $p_i$ units of damage to all enemies within its range. For example, if an enemy is located at cell $(x, y)$ and a tower is at $(x_i, y_i)$ with a range of $r$, then the enemy will take damage of $p_i$ if $(x - x_i) ^ 2 + (y - y_i) ^ 2 \le r ^ 2$.
Enemies move from cell $(1, 1)$ to cell $(n, m)$, visiting each cell of the path exactly once. An enemy instantly moves to an adjacent cell horizontally or vertically, but before doing so, it spends one second in the current cell. If its health becomes zero or less during this second, the enemy can no longer move. The player loses if an enemy reaches cell $(n, m)$ and can make one more move.
By default, all towers have a zero range, but the player can set a tower's range to an integer $r$ ($r > 0$), in which case the health of all enemies will increase by $3^r$. However, each $r$ can only be used for at most one tower.
Suppose an enemy has a base health of $h$ units. If the tower ranges are $2$, $4$, and $5$, then the enemy's health at the start of the path will be $h + 3 ^ 2 + 3 ^ 4 + 3 ^ 5 = h + 9 + 81 + 243 = h + 333$. The choice of ranges is made once before the appearance of enemies and cannot be changed after the game starts.
Find the maximum amount of base health $h$ for which it is possible to set the ranges so that the player does not lose when an enemy with health $h$ passes through (without considering the additions for tower ranges).
InputThe first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases.
The first line of each test case contains three integers $n$, $m$, and $k$ ($2 \le n, m \le 50, 1 \le k < n \cdot m$) — the dimensions of the field and the number of towers on it.
The next $n$ lines each contain $m$ characters — the description of each row of the field, where the character "." denotes an empty cell, and the character "#" denotes a path cell that the enemies will pass through.
Then follow $k$ lines — the description of the towers. Each line of description contains three integers $x_i$, $y_i$, and $p_i$ ($1 \le x_i \le n, 1 \le y_i \le m, 1 \le p_i \le 500$) — the coordinates of the tower and its attack parameter. All coordinates correspond to empty cells on the game field, and all pairs $(x_i, y_i)$ are pairwise distinct.
It is guaranteed that the sum of $n \cdot m$ does not exceed $2500$ for all test cases.
OutputFor each test case, output the maximum amount of base health $h$ on a separate line, for which it is possible to set the ranges so that the player does not lose when an enemy with health $h$ passes through (without considering the additions for tower ranges).
If it is impossible to choose ranges even for an enemy with $1$ unit of base health, output "0".
ExampleInput6 2 2 1 #. ## 1 2 1 2 2 1 #. ## 1 2 2 2 2 1 #. ## 1 2 500 3 3 2 #.. ##. .## 1 2 4 3 1 3 3 5 2 #.### #.#.# ###.# 2 2 2 2 4 2 5 5 4 #.... #.... #.... #.... ##### 3 2 142 4 5 9 2 5 79 1 3 50Output
0 1 1491 11 8 1797Note
In the first example, there is no point in increasing the tower range, as it will not be able to deal enough damage to the monster even with $1$ unit of health.
In the second example, the tower has a range of $1$, and it deals damage to the monster in cells $(1, 1)$ and $(2, 2)$.
In the third example, the tower has a range of $2$, and it deals damage to the monster in all path cells. If the enemy's base health is $1491$, then after the addition for the tower range, its health will be $1491 + 3 ^ 2 = 1500$, which exactly equals the damage the tower will deal to it in three seconds.
In the fourth example, the tower at $(1, 2)$ has a range of $1$, and the tower at $(3, 1)$ has a range of $2$.
Output
你正在玩一个叫做"Runnerfield 2"的非常受欢迎的塔防游戏。在这个游戏中，玩家设置防御塔来攻击从起点到玩家基地的敌人。游戏在一个n*m的网格上进行，已经有k个塔放置好，并且敌人将会沿着一条路径移动。网格交叉点的单元格表示为(x, y)。
每秒，一个塔对其范围内的所有敌人造成p_i单位的伤害。例如，如果一个敌人位于单元格(x, y)，而一个塔位于(x_i, y_i)且范围为r，那么如果(x - x_i)^2 + (y - y_i)^2 <= r^2，敌人将受到p_i的伤害。
敌人从单元格(1, 1)移动到单元格(n, m)，每个单元格的路径恰好经过一次。敌人立即水平或垂直移动到相邻单元格，但在这样做之前，它会花一秒时间在当前单元格。如果在这一秒内其生命值变为零或更低，敌人将不能再移动。如果敌人到达单元格(n, m)并且能够再次移动，玩家将失败。
默认情况下，所有塔的范围都是零，但玩家可以将塔的范围设置为整数r(r > 0)，在这种情况下，所有敌人的生命值将增加3^r。然而，每个r只能用于最多一个塔。
假设一个敌人有h单位的基础生命值。如果塔的范围是2、4和5，那么敌人在路径开始时的生命值将是h + 3^2 + 3^4 + 3^5 = h + 9 + 81 + 243 = h + 333。范围的选择在敌人出现之前一次完成，游戏开始后不能更改。
找出可能设置范围的最大基础生命值h，使得具有h生命值的敌人在通过时不考虑塔范围的增加时玩家不会失败。
输入输出数据格式：
输入：
第一行包含一个整数t(1 ≤ t ≤ 100)——测试用例的数量。
每个测试用例的第一行包含三个整数n、m和k(2 ≤ n, m ≤ 50, 1 ≤ k < n*m)——田地的尺寸和上面的塔的数量。
接下来n行，每行包含m个字符——每一行的描述，其中字符"."表示一个空单元格，字符"#"表示敌人将经过的路径单元格。
然后是k行——塔的描述。每个描述行包含三个整数x_i、y_i和p_i(1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, 1 ≤ p_i ≤ 500)——塔的坐标及其攻击参数。所有坐标对应于游戏场上的空单元格，所有(x_i, y_i)对都是两两不同的。
保证所有测试用例的n*m之和不超过2500。
输出：
对于每个测试用例，输出一个单独的行，其中包含可能设置范围的最大基础生命值h，使得具有h生命值的敌人在通过时不考虑塔范围的增加时玩家不会失败。
如果即使对于生命值为1的敌人也无法选择范围，输出"0"。题目大意： 你正在玩一个叫做"Runnerfield 2"的非常受欢迎的塔防游戏。在这个游戏中，玩家设置防御塔来攻击从起点到玩家基地的敌人。游戏在一个n*m的网格上进行，已经有k个塔放置好，并且敌人将会沿着一条路径移动。网格交叉点的单元格表示为(x, y)。 每秒，一个塔对其范围内的所有敌人造成p_i单位的伤害。例如，如果一个敌人位于单元格(x, y)，而一个塔位于(x_i, y_i)且范围为r，那么如果(x - x_i)^2 + (y - y_i)^2 <= r^2，敌人将受到p_i的伤害。 敌人从单元格(1, 1)移动到单元格(n, m)，每个单元格的路径恰好经过一次。敌人立即水平或垂直移动到相邻单元格，但在这样做之前，它会花一秒时间在当前单元格。如果在这一秒内其生命值变为零或更低，敌人将不能再移动。如果敌人到达单元格(n, m)并且能够再次移动，玩家将失败。 默认情况下，所有塔的范围都是零，但玩家可以将塔的范围设置为整数r(r > 0)，在这种情况下，所有敌人的生命值将增加3^r。然而，每个r只能用于最多一个塔。 假设一个敌人有h单位的基础生命值。如果塔的范围是2、4和5，那么敌人在路径开始时的生命值将是h + 3^2 + 3^4 + 3^5 = h + 9 + 81 + 243 = h + 333。范围的选择在敌人出现之前一次完成，游戏开始后不能更改。 找出可能设置范围的最大基础生命值h，使得具有h生命值的敌人在通过时不考虑塔范围的增加时玩家不会失败。 输入输出数据格式： 输入： 第一行包含一个整数t(1 ≤ t ≤ 100)——测试用例的数量。 每个测试用例的第一行包含三个整数n、m和k(2 ≤ n, m ≤ 50, 1 ≤ k < n*m)——田地的尺寸和上面的塔的数量。 接下来n行，每行包含m个字符——每一行的描述，其中字符"."表示一个空单元格，字符"#"表示敌人将经过的路径单元格。 然后是k行——塔的描述。每个描述行包含三个整数x_i、y_i和p_i(1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, 1 ≤ p_i ≤ 500)——塔的坐标及其攻击参数。所有坐标对应于游戏场上的空单元格，所有(x_i, y_i)对都是两两不同的。 保证所有测试用例的n*m之和不超过2500。 输出： 对于每个测试用例，输出一个单独的行，其中包含可能设置范围的最大基础生命值h，使得具有h生命值的敌人在通过时不考虑塔范围的增加时玩家不会失败。 如果即使对于生命值为1的敌人也无法选择范围，输出"0"。