题目传送门
1 /*
2 题意：问一个点到另一个点的最少转向次数。
3 坐标离散化+BFS：因为数据很大，先对坐标离散化后，三维(有方向的)BFS
4 关键理解坐标离散化，BFS部分可参考HDOJ_1728
5 */
6 #include <cstdio>
7 #include <algorithm>
8 #include <cstring>
9 #include <queue>
10 #include <vector>
11 #include <map>
12 #include <cmath>
13 using namespace std;
14
15 const int MAXN = 8 * 50 + 100;
16 const int INF = 0x3f3f3f3f;
17 vector<int> nx, ny;
18 map<int, int> mx, my;
19 struct Point
20 {
21 int x, y, t, d;
22 Point (int _x = 0, int _y = 0) {x = _x, y = _y, t = 0;}
23 void read(void)
24 {
25 scanf ("%d%d", &x, &y);
26 nx.push_back (x); ny.push_back (y);
27 }
28 void updata(void) {x = mx[x]; y = my[y];}
29 bool operator < (const Point &r) const {return t > r.t;}
30 }s, e, p[55][4];
31 bool maze[2*MAXN][2*MAXN];
32 int dp[MAXN][MAXN][4];
33 bool can[MAXN][MAXN][4];
34 int dx[4] = {0, 1, 0, -1};
35 int dy[4] = {1, 0, -1, 0};
36 int w;
37
38 int compress(vector<int> &x, map<int, int> &mp)
39 {
40 vector<int> xs;
41 sort (x.begin (), x.end ());
42 x.erase (unique (x.begin (), x.end ()), x.end ());
43 for (int i=0; i<x.size (); ++i)
44 {
45 for (int d=-1; d<=1; ++d) xs.push_back (x[i] + d);
46 }
47 sort (xs.begin (), xs.end ());
48 xs.erase (unique (xs.begin (), xs.end ()), xs.end ());
49 for (int i=0; i<xs.size (); ++i) mp[x[i]] = find (xs.begin (), xs.end (), x[i]) - xs.begin ();
50 return xs.size ();
51 }
52
53 bool check(Point &a)
54 {
55 if (0 <= a.x && a.x <= w && 0 <= a.y && a.y <= w && dp[a.x][a.y][a.d] > a.t)
56 {
57 dp[a.x][a.y][a.d] = a.t;
58 return true;
59 }
60 return false;
61 }
62
63 int BFS(void)
64 {
65 memset (dp, INF, sizeof (dp));
66 priority_queue<Point> Q; s.t = 0;
67 for (s.d=0; s.d<4; ++s.d)
68 {
69 Q.push (s); dp[s.x][s.y][s.d] = 0;
70 }
71
72 while (!Q.empty ())
73 {
74 Point now = Q.top (); Q.pop ();
75 if (dp[now.x][now.y][now.d] < now.t) continue;
76 if (now.x == e.x && now.y == e.y) return now.t;
77 for (int d=-1; d<=1; ++d)
78 {
79 Point to = now;
80 to.d = (to.d + 4 + d) % 4;
81 if (!can[to.x][to.y][to.d]) continue;
82 int x = 2 * to.x, y = 2 * to.y;
83 if (maze[x][y] && maze[x+1][y+1] &&
84 ((now.d % 2 == 0 && d != 1) || (now.d % 2 == 1 && d != -1))) continue;
85 if (maze[x+1][y] && maze[x][y+1] &&
86 ((now.d % 2 == 0 && d != -1) || (now.d % 2 == 1 && d != 1))) continue;
87 if (d != 0) to.t++;
88 to.x += dx[to.d]; to.y += dy[to.d];
89 if (check (to)) Q.push (to);
90 }
91 }
92
93 return -1;
94 }
95
96 int main(void) //HDOJ 4444 Walk
97 {
98 // freopen ("C.in", "r", stdin);
99
100 while (true)
101 {
102 nx.clear (); ny.clear (); mx.clear (); my.clear ();
103 s.read (); e.read ();
104 if (!s.x && !s.y && !e.x && !e.y) break;
105 memset (maze, false, sizeof (maze));
106
107 int n; scanf ("%d", &n);
108 for (int i=1; i<=n; ++i)
109 {
110 Point *t = p[i];
111 t[0].read (); t[2].read ();
112 if (t[0].x > t[2].x) swap (t[0], t[2]);
113 if (t[0].y > t[2].y)
114 {
115 Point a = t[0], b = t[2];
116 t[0].y = b.y; t[2].y = a.y;
117 }
118 t[1] = (Point) {t[2].x, t[0].y};
119 t[3] = (Point) {t[0].x, t[2].y};
120 }
121
122 w = max (compress (nx, mx), compress (ny, my));
123 s.updata (); e.updata ();
124 for (int i=1; i<=n; ++i)
125 {
126 Point *t = p[i];
127 for (int j=0; j<4; ++j) t[j].updata ();
128 for (int j=0; j<4; ++j) t[j] = Point (2*t[j].x, 2*t[j].y);
129 for (int j=t[0].x+1; j<=t[2].x; ++j)
130 {
131 for (int k=t[0].y+1; k<=t[2].y; ++k) maze[j][k] = true; //离散化后将矩形涂黑
132 }
133 }
134
135 memset (can, true, sizeof (can));
136 for (int i=0; i<w; ++i)
137 {
138 for (int j=0; j<w; ++j)
139 {
140 int x = i * 2, y = j * 2;
141 bool *d = can[i][j];
142 if (maze[x][y+1] && maze[x+1][y+1]) d[0] = false; //判断4个方向能不能走
143 if (maze[x+1][y] && maze[x+1][y+1]) d[1] = false;
144 if (maze[x][y] && maze[x+1][y]) d[2] = false;
145 if (maze[x][y] && maze[x][y+1]) d[3] = false;
146 }
147 }
148
149 printf ("%d\n", BFS ());
150 }
151
152 return 0;
153 }
