题目描述(ID:12356)
标题: 导航(Cow Navigation)
标签: 搜索 广度优先搜索
详情:
啊哈沃德进入了编程星球的一关迷宫中。已知迷宫是一个N*N2<=N<=20)的矩形,其中有些部分可以通行(E),有些部分则被阻拦了起来(H)。啊哈沃德正处在坐标(11)的位置,他需要前进到坐标(NN)的位置。困难之处在于,啊哈沃德并不知道他目前的面向是朝着(12)还是(21)。

你可以用编程星球中的三种指令:前进、左转、右转来控制啊哈沃德。对于某一条命令,如果啊哈沃德可以执行,他就会执行操作,而如果不能执行(如前进道路上有障碍),他就会跳过这条命令执行后续操作。而如果啊哈沃德已经到达了终点,他就会忽略后续的所有其他命令。

在这种情况下,给定迷宫,请你帮助计算,能够保证啊哈沃德在无论起点朝向(12)还是(21)的情况下,都能抵达终点的最短指令是多少条?
输入格式:
第一行是一个整数N(2<=N<=20)
接下来N行每行有一个长度为N的字符串,合起来构成迷宫的地图,可以通行的地方为E,不能通行的地方为H。且保证(1,1)和(N,N)必定是可以通行的
输出格式:
输出一个数字,为无论啊哈沃德朝向为何时,都能保证抵达终点的最短代码行数
提示: 本题改编自USACO 2018 Cow Navigation
样例:

输入

3
EHE
EEE
EEE

输出

9

解释

采用:前进、右转、前进、前进、左转、前进、左转、前进、前进9条命令,无论啊哈沃德面向何方,都能够抵达终点。
登录并解答