题目名称	161. [USACO Oct07] 障碍训练场
输入输出	`obstacle.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	25
题目来源	BYVoid 于2008-10-07加入
开放分组	全部用户
提交状态
分类标签	USACO 动态规划搜索法
	分享题解

通过：104，提交：245，通过率：42.45%
liu_runda	100	0.015 s	0.42 MiB	C++
我	100	0.018 s	0.44 MiB	C++
GROWL GOOD BOYส็	100	0.019 s	0.36 MiB	C++
lszjl	100	0.020 s	0.36 MiB	C++
_Horizon	100	0.021 s	0.46 MiB	C++
水中音	100	0.022 s	0.33 MiB	C++
Aglove	100	0.022 s	0.68 MiB	C++
zys	100	0.023 s	0.51 MiB	C++
/k	100	0.028 s	0.36 MiB	C++
Czb。	100	0.032 s	0.39 MiB	C++

关于障碍训练场的近10条评论(全部评论)
为啥我这个不是最优选择斯内普和骑士 2019-05-22 17:05 6楼
为什么我的算法不是最优解呜呜呜呜斯内普和骑士 2019-05-08 16:41 5楼
memset太慢了，若用的话会超时； forever 2015-06-12 21:06 4楼
筽邝 2014-09-13 17:40 3楼
回复 @Truth.Cirno : +1 水中音 2014-08-30 10:33 2楼
改编自“激光电话” Truth.Cirno 2012-10-14 17:37 1楼

161. [USACO Oct07] 障碍训练场

★☆ 输入文件：obstacle.in 输出文件：obstacle.out 简单对比
时间限制：1 s 内存限制：128 MiB

译 By CmYkRgB123

【题目描述】

考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了'x'。例如下图：

 . . B x .
        . x x A .
        . . . x .
        . x . . .
        . . x . .

贝茜发现自己恰好在点A出，她想去B处的盐块添盐。缓慢而且笨拙的动物，比如奶牛，十分讨厌转弯。尽管如此，当然在必要的时候她们还是会转弯的。对于一个给定的牧场，请你计算从A到B最少的转弯次数。开始的时候，贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。

【输入格式】

行 1: 一个整数 N
行 2..N + 1: 行 i+1 有 N 个字符 ('.', 'x', 'A', 'B')，表示每个点的状态。

【输出格式】

行 1: 一个整数，最少的转弯次数。

【输入样例】

3
.xA
...
Bx.

【输出样例】