111qqz的小窝

老年咸鱼冲锋!

BZOJ 1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 (BFS,DP)

 

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 451  Solved: 226
[Submit][Status][Discuss]

Description

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

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

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

Input

第 1行: 一个整数 N 行

2..N + 1: 行 i+1 有 N 个字符 (‘.’, ‘x’, ‘A’, ‘B’),表示每个点的状态。

Output

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

Sample Input

3
.xA

Bx.

Sample Output

2
思路:bfs.我一开始的错误做法是用优先队列,以转弯数为关键字。
但是实际上错的,因为到达同一个点可能之后到达的方法有更少的转弯数,但是在做bfs的时候,之前访问的节点已经被标记了,所以无法更新成更优的值。
正解是类似dp的做法。需要注意不需要vis数组标记。
用dir[x][y][i]表示从i方向到达x,y的需要转弯数。
初始dir[s.x][s.y][0..3]为0,其余为inf

然后更新的时候如果dir[fx][fy][i]=min(dir[x][y][j]+1) 当i!=j

dir[fx][fy][i]=min(dir[x][y][j]) 当i=j

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz