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
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月10日 星期日 17时00分22秒
4File Name :code/bzoj/1644.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34char maze[N][N];
35int n;
36bool vis[N][N];
37int dir[N][N][5];
38struct node
39{
40 int x,y;
41
42
43 bool ok ()
44 {
45 if (x>=0&&x<n&&y>=0&&y<n&&maze[x][y]!='x') return true;
46 return false;
47 }
48
49 void look()
50 {
51 cout<<"x:"<<x<<" y:"<<y<<endl;
52 }
53
54}s,e;
55
56void bfs()
57{
58 queue<node>q;
59 q.push(s);
60
61 while (!q.empty())
62 {
63 node pre = q.front(); q.pop();
64// pre.look();
65 for ( int i = 0 ; i < 4 ; i++)
66 {
67 node nxt;
68 nxt.x = pre.x + dx4[i];
69 nxt.y = pre.y + dy4[i];
70 if (!nxt.ok()) continue;
71 for ( int j = 0 ; j < 4 ; j++)
72 {
73 bool flag = false;
74 if (i==j&&dir[nxt.x][nxt.y][i]>dir[pre.x][pre.y][j])
75 {
76 dir[nxt.x][nxt.y][i] = dir[pre.x][pre.y][j];
77 flag = true;
78 }
79 if (i!=j&&dir[nxt.x][nxt.y][i]>dir[pre.x][pre.y][j]+1)
80 {
81 dir[nxt.x][nxt.y][i] = dir[pre.x][pre.y][j] + 1;
82 flag = true;
83 }
84 if (flag)
85 {
86 q.push(nxt);
87 }
88
89 }
90 }
91 }
92}
93int main()
94{
95 #ifndef ONLINE_JUDGE
96 freopen("code/in.txt","r",stdin);
97 #endif
98
99 scanf("%d",&n);
100 for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
101
102 for ( int i = 0 ; i < n ; i ++)
103 for ( int j = 0 ; j < n ; j++)
104 {
105 if (maze[i][j]=='A')
106 {
107 s.x = i ;
108 s.y = j;
109 }
110 if (maze[i][j]=='B')
111 {
112 e.x = i ;
113 e.y = j ;
114 }
115 }
116
117 ms(dir,0x3f);
118 for ( int i = 0 ; i < 4 ; i++) dir[s.x][s.y][i] = 0;
119 bfs();
120// for ( int i = 0 ; i < 4 ; i++) cout<<dir[e.x][e.y][i]<<endl;
121 int ans = inf;
122 for ( int i = 0 ; i < 4 ; i++) ans = min(ans,dir[e.x][e.y][i]);
123 printf("%d\n",ans);
124
125 return 0;
126}