Cow Navigation

题目描述

贝茜又一次被困在了农夫约翰谷仓的错误一侧，由于她视力很差，她需要你帮助她在谷仓中导航。 谷仓由一个 $N \times N$ 的方格网格组成（$2 \leq N \leq 20$），其中一些格子是空的，一些格子包含无法通过的干草捆。 贝茜从左下角（格子 1,1）出发，想要移动到右上角（格子 $N,N$）。你可以通过给她一串指令来引导她，每条指令只能是以下三种之一：“前进”、“左转 90 度”或“右转 90 度”。你希望给出最短的指令序列，使她到达目的地。 如果你指示贝茜走出网格（即撞到谷仓墙）或走进干草捆，她将不会移动，并会跳到序列中的下一条指令。 不幸的是，贝茜并不知道她起初是面朝上（朝向格子 1,2）还是面朝右（朝向格子 2,1）。你需要给出一串最短的指令，使她无论哪种初始朝向都能到达目标。 一旦她到达目标，她将忽略后续指令。

输入格式

第一行输入 $N$。 接下来的 $N$ 行每行包含一个长度恰好为 $N$ 的字符串，表示谷仓。最后一行的第一个字符对应格子 1,1。第一行的最后一个字符对应格子 N, N。 每个字符要么是 H 表示干草捆，要么是 E 表示空格。 保证格子 1,1 和 $N,N$ 为空，并且保证存在一条由空格组成的路径，从格子 1,1 通到格子 $N, N$。

输出格式

输出一行：输出最短指令序列的长度，使贝茜无论起初面朝上还是面朝右都能到达目标。

3
EHE
EEE
EEE

9

提示

在该示例中，指令序列“前进、右转、前进、前进、左转、前进、左转、前进、前进”将引导贝茜到达目的地，而不受其初始朝向影响。 题目来源：Brian Dean

标签: USACO|2017|Gold

来源

USACO|2017|Gold