P1382. 正确的钥匙

题目描述

许多人认为俄罗斯方块是由两位俄罗斯程序员发明的。但这并非全部真相。这个游戏的想法非常古老——甚至古埃及人也有类似的东西。但他们并没有将其用作游戏，而是用作一种非常复杂的锁。这把锁由木头制成，由大量方形区域组成，排列成整齐的行和列。每个区域要么完全由木头填充，要么是空的。这把锁的钥匙是二维的，通过连接与锁区域大小相同的方形部件制成。因此，他们有一个2D锁和一个可以从顶部插入锁中的2D钥匙。钥匙的设计使得无法向上移动它，只能向下掉落或左右滑动——就像俄罗斯方块游戏一样。唯一的区别是钥匙不能旋转。旋转功能确实是俄罗斯人的发明。

金字塔的入口大门就有这样一把锁。ACM考古学家找到了几把钥匙，其中一把极有可能属于这把锁。现在他们需要尝试这些钥匙，找出应该使用哪一把。由于尝试所有钥匙太耗时，最好从那些可以插入锁中更深的钥匙开始。你的程序需要确定给定钥匙可以插入给定锁中的最大深度。

输入格式

输入包含$T$个测试用例。第一行给出测试用例的数量$T$。每个测试用例以一行两个整数$R$和$C$（$1 \leq R,C \leq 100$）开始，表示钥匙的大小。接下来是$R$行，每行包含$C$个字符。每个字符是井号(#)或点(.)。井号表示一个由木头填充的方形区域；点表示空区域。木制区域总是连通的，即整个钥匙由一块组成。此外，即使从顶部任意切割掉若干行，钥匙仍保持连通。顶部行、底部行、最左列和最右列至少有一个非空区域。

钥匙描述后，有一行包含两个整数$D$和$W$（$1 \leq D \leq 10000$, $1 \leq W \leq 1000$）。$W$是锁的宽度，$D$是锁的深度。接下来的$D$行每行包含$W$个字符，可能是井号（表示木头）或点（表示自由空间）。

输出格式

对于每个测试用例，你的程序应输出一行。该行应包含语句"The key falls to depth X."，其中$X$是钥匙可以通过仅向下移动和左右滑动插入的最大深度。深度是钥匙底部与锁顶部之间的距离。如果钥匙可以穿过整个锁并从底部移出，则输出句子"The key can fall through."。

示例输入

4
2 4
#.##
###.
3 6
#....#
#....#
#..###
2 3
##.
.##
2 7
#.#.#.#
.#.#.#.
1 1
#
1 10
###....###
3 2
##
.#
.#
1 5
#.#.#

示例输出

The key falls to depth 2.
The key falls to depth 0.
The key can fall through.
The key falls to depth 2.

来源

Central Europe 1999