SP3387 CHMAZE - Changing Maze

卢克·天行者和他的妹妹兼爱人莱娅在尝试穿越一个致命的迷宫。这个迷宫可谓危机四伏！每过一段时间，迷宫的边界会发生变化。如果卢克和莱娅在变化的时刻恰好到了一个出现边界的格子上，他们就命不保夕。不过别担心，原力会指引他们安全通过迷宫，只是原力需要你的建议来调整策略。 卢克和莱娅从迷宫的西北角出发，目标是到达东南角。在每个时间步内，卢克和莱娅可以选择向北、南、东、西四个方向移动一格，或者选择原地不动。同时，迷宫的边界也会随时间步发生变化：会有一个有限的边界模式列表；如果他们还未成功到达目的地且模式列表已经用尽，迷宫会从第一个模式重新开始循环。你需要计算出卢克和莱娅是否能够成功到达迷宫的东南角，并在可以到达的情况下，确定所需的最少时间步数。请记住，这关系到原力的关键意图！如果你的建议不当，可能会让我们苦苦等待《新的新希望》，而壁上观望将会是多么漫长！

输入包含若干个测试用例。每个测试用例（最后一个除外）开始于一行，包含三个十进制整数，分别表示迷宫的行数、列数和边界模式的数量。行数和列数在 $1$ 到 $20$ 之间（包括 $1$ 和 $20$），模式数量在 $1$ 到 $10$ 之间（包括 $1$ 和 $10$）。这些整数之间以一个空格分隔，行末有一个换行符。随后是多个模式，每个模式包含 $r$ 行，每行有 $c$ 个字符，这里 $r$ 和 $c$ 分别为迷宫的行数和列数。每个字符为 $0$（表示无边界）或 $1$（表示有边界）。每行之后是一个换行符，每个模式后再加一个额外的换行符。第一个模式的西北角总为 $0$，因为卢克和莱娅从此处开始。最后一个测试用例由三个零构成，彼此之间以空格分隔，并以换行符结尾，提示输入结束，不需处理。

对于每个测试用例，输出顺序与输入相同。每种情况有以下两种输出之一： - `Case c: Luke and Leia can escape in s steps.` - `Case c: Luke and Leia cannot escape.` 其中 $c$ 是当前测试用例的编号（从 $1$ 开始），$s$ 是卢克和莱娅成功到达东南角所需的最短时间步数。每行的末尾都应为一个换行符。 **本翻译由 AI 自动生成**