SP10571 SOCCERCH - Soccer Challenge

一个足球场被划分为 $N$ 行 $M$ 列的方格。每个方格的边长为 1。费尔南多喜欢沿着方格的边缘跑步，并且他不愿进入方格内部。 场地中有部分方格上是泥泞的，而另一些方格则被费尔南多选为目标方格。方格可以既不是泥泞的也不是目标的。 费尔南多从左上角开始，他想经过整个场地并返回起点。由他的路径围成的区域内的所有方格都视为已检查。更具挑战性的是，他希望除了起点之外，路径不要与自身相交。不过，好在方格的边缘足够宽阔，使他可以多次沿着同一条边走而不与自己的路径相交。 费尔南多的目标是检查所有目标方格，但不能经过泥泞的方格。对手队的马丁则提出挑战，表示他能从右下角出发找出一条更短的路径。你能帮助费尔南多找出最短路径，并判断他的路径是否短于马丁的路径吗？

输入包括多个测试用例。 每个测试用例的第一行包含两个整数 $R$ 和 $C$（$1 \le R, C \le 50$），表示足球场的行数和列数。 接下来有 $R$ 行，每行由 $C$ 个字符构成，用来描述足球场。这些字符分别为 `I`（目标方格，需检查），`X`（泥泞方格）和 `O`（普通方格）。目标方格和泥泞方格的总数不会超过 10。 行与行之间没有多余的空格。 输入的最后以一行 "0 0" 结束，此行不需处理。

对于每个测试用例，输出一行。如果费尔南多或马丁中某一人的路径更短，输出该选手的名字和路径长度；如果他们双方路径相同，则输出 "Tie"，后面跟路径长度。此长度即为检查目标方格无需经过泥泞方格的最短路径长度。 **本翻译由 AI 自动生成**