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
/* ***********************************************
Author :111qqz
Created Time :2016年04月10日 星期日 17时00分22秒
File Name :code/bzoj/1644.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=105;
7char maze[N][N];
8int n;
9bool vis[N][N];
10int dir[N][N][5];
11struct node
12{
13 int x,y;
1 bool ok ()
2 {
3 if (x>=0&&x<n&&y>=0&&y<n&&maze[x][y]!='x') return true;
4 return false;
5 }
1 void look()
2 {
3 cout<<"x:"<<x<<" y:"<<y<<endl;
4 }
}s,e;
1void bfs()
2{
3 queue<node>q;
4 q.push(s);
1 while (!q.empty())
2 {
3 node pre = q.front(); q.pop();
4// pre.look();
5 for ( int i = 0 ; i < 4 ; i++)
6 {
7 node nxt;
8 nxt.x = pre.x + dx4[i];
9 nxt.y = pre.y + dy4[i];
10 if (!nxt.ok()) continue;
11 for ( int j = 0 ; j < 4 ; j++)
12 {
13 bool flag = false;
14 if (i==j&&dir[nxt.x][nxt.y][i]>dir[pre.x][pre.y][j])
15 {
16 dir[nxt.x][nxt.y][i] = dir[pre.x][pre.y][j];
17 flag = true;
18 }
19 if (i!=j&&dir[nxt.x][nxt.y][i]>dir[pre.x][pre.y][j]+1)
20 {
21 dir[nxt.x][nxt.y][i] = dir[pre.x][pre.y][j] + 1;
22 flag = true;
23 }
24 if (flag)
25 {
26 q.push(nxt);
27 }
1 }
2 }
3 }
4}
5int main()
6{
7 #ifndef ONLINE_JUDGE
8 freopen("code/in.txt","r",stdin);
9 #endif
scanf("%d",&n);
for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
1 for ( int i = 0 ; i < n ; i ++)
2 for ( int j = 0 ; j < n ; j++)
3 {
4 if (maze[i][j]=='A')
5 {
6 s.x = i ;
7 s.y = j;
8 }
9 if (maze[i][j]=='B')
10 {
11 e.x = i ;
12 e.y = j ;
13 }
14 }
1 ms(dir,0x3f);
2 for ( int i = 0 ; i < 4 ; i++) dir[s.x][s.y][i] = 0;
3 bfs();
4// for ( int i = 0 ; i < 4 ; i++) cout<<dir[e.x][e.y][i]<<endl;
5 int ans = inf;
6 for ( int i = 0 ; i < 4 ; i++) ans = min(ans,dir[e.x][e.y][i]);
7 printf("%d\n",ans);
return 0;
}