BZOJ 1656: [Usaco2006 Jan] The Grove 树木(神奇的bfs之射线法)
1656: [Usaco2006 Jan] The Grove 树木
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 143 Solved: 88 [Submit][Status][Discuss]
Description
The pasture contains a small, contiguous grove of trees that has no ‘holes’ in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She’s just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn’t think you could pass ’through’ the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take. Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here’s a typical example where ‘.’ is pasture (which Bessie may traverse), ‘X’ is the grove of trees, ‘’ represents Bessie’s start and end position, and ‘+’ marks one shortest path she can walk to circumnavigate the grove (i.e., the answer): …+… ..+X+.. .+XXX+. ..+XXX+ ..+X..+ …+++ The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she’s starting ‘outside’ the grove instead of in a sort of ‘harbor’ that could complicate finding the best path.
牧场里有一片树林，林子里没有坑．
贝茜很想知道，最少需要多少步能围绕树林走一圈，最后回到起点．她能上下左右走，也能走对角线格子．牧场被分成R行C列(1≤R≤50，1≤C≤50)．下面是一张样例的地图，其中“．”表示贝茜可以走的空地， “X”表示树林， “*”表示起点．而贝茜走的最近的路已经特别地用“+”表示出来．
题目保证，最短的路径一定可以找到．
Input
Line 1: Two space-separated integers: R and C
Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).
第1行输入R和C，接下来R行C列表示一张地图．地图中的符号如题干所述．
Output
- Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.
输出最少的步数．
Sample Input
6 7 ……. …X… ..XXX.. …XXX. …X… ……*
Sample Output
13
思路：我的思路是错的。。就不说了。。这题太神辣。。。用来求解绕过某一区域的最短路。。做法是找一个点做一条平行于边界的射线（单向）到另一边界。
射线法大概就是：如果和多变形交了奇数次，就说明在多边形内部，否则在外部。
讲真。。还不是特别明白。。。感觉和计算几何比较有关系。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月14日 星期四 22时29分15秒
4File Name :code/bzoj/1656.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 dx8[8]={1,1,1,0,0,-1,-1,-1};
33const int dy8[8]={1,0,-1,1,-1,1,0,-1};
34const int inf = 0x3f3f3f3f;
35const int N=55;
36char maze[N][N];
37int n,m;
38int ans;
39int f[2][N][N];//f[k][i][j]表示的是从起点走到(i,j),射线法与多边形交点的奇偶性的k的最短路。
40//起点为f[0][s.x][s.y],答案为f[1][s.x][s.y];
41bool die[N][N]; //画一条射线。。
42struct node
43{
44 int x,y;
45 int f;//f表示改点射线法与多边形交点的奇偶性。
46
47 bool ok()
48 {
49 if (x>=0&&x<n&&y>=0&&y<m&&maze[x][y]!='X') return true;
50 return false;
51 }
52}s,tree;
53
54
55void bfs()
56{
57 queue<node>q;
58 s.f = 0;
59 q.push(s);
60
61 while (!q.empty())
62 {
63 node pre = q.front() ; q.pop();
64 for ( int i = 0 ; i < 8 ; i++)
65 {
66 node nxt;
67 nxt.x = pre.x + dx8[i];
68 nxt.y = pre.y + dy8[i];
69 if (!nxt.ok()) continue;
70 if ((die[pre.x][pre.y]||die[nxt.x][nxt.y])&&nxt.y<=pre.y) continue;
71 if (die[nxt.x][nxt.y]&&!f[1][nxt.x][nxt.y])
72 {
73 f[1][nxt.x][nxt.y] = f[pre.f][pre.x][pre.y]+1;
74 nxt.f = 1;
75 q.push(nxt);
76 }else if (!f[pre.f][nxt.x][nxt.y])
77 {
78 f[pre.f][nxt.x][nxt.y] = f[pre.f][pre.x][pre.y] + 1;
79 nxt.f = pre.f;
80 q.push(nxt);
81 }
82 }
83 }
84
85}
86int main()
87{
88 #ifndef ONLINE_JUDGE
89 freopen("code/in.txt","r",stdin);
90 #endif
91
92 scanf("%d %d",&n,&m);
93 for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
94
95 for ( int i = 0 ; i < n ; i++)
96 {
97 for ( int j = 0 ; j < m ; j++)
98 {
99 if (maze[i][j]=='*')
100 {
101 s.x = i ;
102 s.y = j;
103 }
104 if (maze[i][j]=='X')
105 {
106 tree.x = i ;
107 tree.y = j;
108 }
109 }
110 }
111
112 ms(die,false);
113 for ( int i = 0 ; i < n ; i++) if (i+tree.x<n) die[i+tree.x][tree.y] = true;
114
115 bfs();
116 printf("%d\n",f[1][s.x][s.y]);
117
118 #ifndef ONLINE_JUDGE
119 fclose(stdin);
120 #endif
121 return 0;
122}