P4442 [COCI 2017/2018 #3] Portal

本任务的主角 Chell 必须解决 GLaDOS 提出的新谜题。 Chell 处于一个房间中，该房间的布局可以表示为一个 N 行 M 列的矩阵。每个格子可以是以下几种之一： - 障碍格子 - 其中有一面墙（用 '#' 表示）， - Chell 的起始位置（用 'C' 表示）， - Chell 必须到达以解决谜题的格子（用 'F' 表示），或者 - 空格子（用 '.' 表示）。 Chell 携带一个所谓的传送枪，可以用来在墙上创建传送门。 在每次移动中，她可以执行以下操作之一： - 向相邻的格子移动，方向可以是上、下、左或右（她不能移动到有墙的格子）。此移动耗时一个单位时间。 - 通过转向一个方向（不一定是相邻的）朝墙射击来在墙上创建一个传送门。传送门只会在被击中的墙的一侧创建。在任何时刻，**最多只能有两个传送门是激活的**。如果在已有两个激活传送门的情况下创建新的传送门，最早创建的那个将消失。不能在已有传送门的位置创建新的传送门。此操作耗时可忽略不计，即零时间。 - 如果她在一个与墙相邻的格子并且墙的这一侧有传送门，她可以进入传送门并从另一个传送门出来到一个非障碍格子。此操作在有两个激活传送门时才可能，并且耗时一个单位时间。 Chell 想知道解决谜题的最少时间，即到达标记为 'F' 的格子的时间。 **请注意**：房间的四周总是有墙，并且字母 'C' 和 'F' 在矩阵中只出现一次。

输入的第一行包含正整数 N 和 M (4 ≤ N, M ≤ 500)，即任务中的数字。 接下来的 N 行中的每一行包含 M 个字符，描述房间的布局。

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

在总分的 50% 的测试用例中，将满足 4 ≤ N, M ≤ 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 提供。