题目描述

本任务的主角 Chell 必须解决 GLaDOS 提出的新谜题。

Chell 处于一个房间中，该房间的布局可以表示为一个 $N$ 行 $M$ 列的矩阵。每个格子可以是以下几种之一：

• 障碍格子 - 其中有一面墙（用 '#' 表示），
• Chell 的起始位置（用 'C' 表示），
• Chell 必须到达以解决谜题的格子（用 'F' 表示），或者
• 空格子（用 '.' 表示）。

Chell 携带一个所谓的传送枪，可以用来在墙上创建传送门。

在每次移动中，她可以执行以下操作之一：

• 向相邻的格子移动，方向可以是上、下、左或右（她不能移动到有墙的格子）。此移动耗时一个单位时间。
• 通过转向一个方向（不一定是相邻的）朝墙射击来在墙上创建一个传送门。传送门只会在被击中的墙的一侧创建。在任何时刻，最多只能有两个传送门是激活的。如果在已有两个激活传送门的情况下创建新的传送门，最早创建的那个将消失。不能在已有传送门的位置创建新的传送门。此操作耗时可忽略不计，即零时间。
• 如果她在一个与墙相邻的格子并且墙的这一侧有传送门，她可以进入传送门并从另一个传送门出来到一个非障碍格子。此操作在有两个激活传送门时才可能，并且耗时一个单位时间。

Chell 想知道解决谜题的最少时间，即到达标记为 'F' 的格子的时间。

请注意：房间的四周总是有墙，并且字母 'C' 和 'F' 在矩阵中只出现一次。

输入格式

输入的第一行包含正整数 $N$ 和 $M$（$4 \le N, M \le 500$），即任务中的数字。

接下来的 $N$ 行中的每一行包含 $M$ 个字符，描述房间的布局。

输出格式

你必须输出解决谜题所需的最少时间，或者如果无法解决则输出 "nemoguce"（不带引号，克罗地亚语表示不可能）。

4 4
####
#.F#
#C.#
####

2

6 8
########
#.##..F#
#C.##..#
#..#...#
#.....##
########

4

4 5
#####
#C#.#
###F#
#####

nemoguce

提示

在总分的 $50\%$ 的测试用例中，将满足 $4 \le N, M \le 15$。

第二个测试用例的说明：

该谜题可以在 $8$ 步内解决，如下图所示。

在第一步中，我们转向左侧墙壁，射击并创建一个传送门，该传送门出现在第 $3$ 行第 $1$ 列（坐标 $(3,1)$）的墙的右侧。

在第二步中，我们从墙的上侧在坐标 $(6,2)$ 创建一个传送门。

在第三步中，我们进入坐标 $(3,1)$ 的传送门并在坐标 $(5,2)$ 出口——一个有第二个传送门的非障碍格子。

在第四步中，我们向右转并从墙的左侧在坐标 $(5,7)$ 创建一个传送门。由于已经有两个传送门，位于 $(3,1)$ 的传送门消失。

在第五步中，我们进入坐标 $(6,2)$ 的传送门并在坐标 $(5,6)$ 出口。

在第六步中，我们从墙的下侧在坐标 $(1,6)$ 创建一个新传送门，使得坐标 $(6,2)$ 的传送门消失。

在第七步中，我们进入坐标 $(5,7)$ 的传送门并在坐标 $(2,6)$ 出口。最后，在第八步中，我们向右移动一格以结束游戏。

第 $1$、$2$、$4$ 和 $6$ 步中的传送门创建耗时为零，而其余移动耗时一个单位时间，因此解决谜题总共需要 $4$ 个单位时间。

题面翻译由 ChatGPT-4o 提供。