CF1955H.The Most Reckless Defense

你正在玩一款非常流行的塔防游戏“Runnerfield 2”。在这款游戏中，玩家需要布置防御塔来攻击从起点移动到玩家基地的敌人。

给定一个 $n \times m$ 的网格，其中已经放置了 $k$ 个防御塔，并且有一条敌人会经过的路径。第 $x$ 行第 $y$ 列的格子记作 $(x, y)$。

每秒钟，每个防御塔会对其攻击范围内的所有敌人造成 $p_i$ 点伤害。例如，如果敌人在格子 $(x, y)$，而防御塔在 $(x_i, y_i)$，攻击范围为 $r$，那么如果满足 $(x - x_i)^2 + (y - y_i)^2 \le 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$。

如果即使敌人基础生命值为 $1$ 也无法获胜，则输出 $0$。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n, m \le 50, 1 \le k < n \cdot m$），表示场地的尺寸和防御塔数量。

接下来 $n$ 行，每行包含 $m$ 个字符，描述场地的每一行，其中字符“.”表示空格子，字符“#”表示敌人会经过的路径格子。

接下来 $k$ 行，每行包含三个整数 $x_i$、$y_i$、$p_i$（$1 \le x_i \le n, 1 \le y_i \le m, 1 \le p_i \le 500$），表示防御塔的坐标和攻击参数。所有坐标均对应于场地上的空格子，且所有 $(x_i, y_i)$ 两两不同。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $2500$。

对于每个测试用例，输出一个整数，表示能够设置攻击范围，使得敌人以基础生命值 $h$ 通过且玩家不会失败的最大 $h$（不考虑因设置攻击范围而增加的生命值）。

如果即使敌人基础生命值为 $1$ 也无法获胜，则输出 $0$。

在第一个样例中，增加防御塔的攻击范围没有意义，即使敌人只有 $1$ 点生命值也无法击败。

在第二个样例中，防御塔的攻击范围为 $1$，它会在 $(1, 1)$ 和 $(2, 2)$ 两个格子对敌人造成伤害。

在第三个样例中，防御塔的攻击范围为 $2$，它会在所有路径格子对敌人造成伤害。如果敌人的基础生命值为 $1491$，那么加上攻击范围带来的生命值后为 $1491 + 3^2 = 1500$，正好等于防御塔在三秒内对敌人造成的伤害。

在第四个样例中，$(1, 2)$ 处的防御塔攻击范围为 $1$，$(3, 1)$ 处的防御塔攻击范围为 $2$。

由 ChatGPT 4.1 翻译