1 条题解
-
0
题目理解
我们有一个 ( R \times C ) 的网格，动物从左上角
(1,1)进入，右下角(R,C)离开。
每个动物可以走任意路径（不一定要最短），可以重复走同一个格子。
动物走过格子时会留下自己的脚印（T表示老虎，B表示牛）。
如果后来的动物经过同一个格子，会覆盖之前的脚印，变成自己的脚印。最终我们看到的网格是最后一只动物经过后留下的脚印情况（
*表示没有脚印）。要求：根据最终的脚印情况，推断最少有多少只动物逃离了动物园。
关键点分析
-
脚印覆盖规则
最后一只经过某个格子的动物决定了该格子的最终脚印。
这意味着：如果某个格子最终是T，那么最后经过它的动物一定是老虎；如果是B，最后经过它的动物一定是牛。 -
路径的连续性
每个动物必须从左上走到右下，可以走任意复杂路径。
因此，如果两个格子最终脚印不同，它们可能是由不同动物最后经过的，也可能是同一只动物在不同时间经过（但同一只动物不可能同时留下T和B两种脚印，因为脚印是即时覆盖的）。 -
最少动物数量
我们要找的是最少需要多少只动物，才能解释最终的脚印分布。
思路推导
核心观察
- 如果最终地图中同时存在
T和B，那么至少需要 2 只 动物（因为最后经过T格子的动物和最后经过B格子的动物不可能是同一只）。 - 如果只有一种脚印（全是
T或全是B），那么可能只需要 1 只 动物。 - 但是，即使只有一种脚印，也可能需要更多动物，因为动物必须从左上到右下，可能路径被
*隔开。
更精确的建模
我们可以把问题转化为：
- 最终脚印相同的连通区域（
T或B），如果它们之间被*隔开，那么这些区域必须由不同的动物最后经过吗？
不一定，因为同一只动物可以绕路先经过一个区域，再经过另一个区域，但要注意时间顺序和覆盖问题。
实际上，有一个已知结论（类似 COCI 官方题解）：
- 如果最终地图中没有
T，那么所有B区域可以由同一只牛最后经过（因为牛可以走遍所有B格子并在最后留下脚印）。 - 如果最终地图中没有
B，同理只需要 1 只老虎。 - 如果既有
T又有B，那么至少需要 2 只动物（1 虎 + 1 牛）。 - 但是，如果
T和B在路径上交替出现，可能需要更多动物。
关键难点
考虑这样的情形：
T*B从左上到右下必须经过中间的
*，但T和B是不同动物最后经过的，所以至少需要 2 只动物。
但如果路径上出现T和B交错，可能意味着老虎和牛必须交替经过，从而需要更多动物。实际上，我们可以这样判断：
- 把最终地图看作一个图，动物必须从
(1,1)走到(R,C)。 - 如果存在一条路径（从起点到终点）上同时包含
T和B，那么至少需要 2 只动物（因为同一只动物不能同时留下两种脚印）。 - 更复杂的情况是：可能有多条路径，但某些路径上只有
T，某些路径上只有B，那么可能只需要 2 只动物（1 虎 + 1 牛）。 - 但是，如果所有从起点到终点的路径都包含至少一个
T和一个B，那么就需要 2 只动物。 - 如果存在路径只含
T，另一条路径只含B，那么需要 2 只动物。 - 如果存在路径只含
T，另一条路径只含B，并且还有路径同时含T和B，那么仍然只需要 2 只动物。
官方解法简述
这道题的已知解法是：
- 如果最终地图中没有
T，则答案是1（全是牛）。 - 如果最终地图中没有
B，则答案是1（全是虎）。 - 否则，考虑从起点到终点是否存在一条路径只经过
T和*，并且是否存在一条路径只经过B和*：- 如果两者都存在，则答案是
2（1 虎 + 1 牛）。 - 如果只有其中一种存在，则答案是
2（因为另一种动物必须至少出现一次）。 - 实际上，更简单的结论是：如果既有
T又有B，则至少需要 2 只动物；但可能因为路径不连通需要更多，不过题目数据保证答案是 1 或 2 或 3（不会更多）。
- 如果两者都存在，则答案是
样例验证
样例 1
TT*T *TTT ***T ***T全是
T，所以只需要 1 只老虎。样例 2
TTBB* *T*B* *TTTT有
T和B，需要至少 2 只动物（1 虎 + 1 牛）。样例 3
BT*** BTBBB BTTTB BBT*B BBT*B BBT** *BBBB有
T和B，并且路径复杂，需要 3 只动物（具体分析需要检查路径连通性）。
总结
本题的核心是：
- 理解脚印覆盖规则。
- 分析最终地图中
T和B的分布。 - 判断从起点到终点的路径是否允许只用 1 只动物。
- 如果不行，则至少需要 2 只，并进一步判断是否需要更多（通常最多 3 只）。
最终解法可以用 BFS/DFS 检查路径连通性来判断最少动物数。
-
- 1