好久沒(méi)貼題了。
貼個(gè)吧。
Robot
Time Limit:1000MS Memory Limit:65536K
Total Submit:590 Accepted:208
Description
Let (x1, y1), …, (xn, yn) be a collection of n points in a two-dimensional plane. Your goal is to navigate a robot from point (x1, y1) to point (xn, yn). From any point (xi, yi), the robot may travel to any other point (xj, yj) at most R units away at a speed of 1 unit per second. Before it does this, however, the robot must turn until it faces (xj, yj); this turning occurs at a rate of 1 degree per second.
Compute the shortest time needed for the robot to travel from point (x1, y1) to (xn, yn). Assume that the robot initially faces (xn, yn). To prevent floating-point precision issues, you should use the double data type instead of float. It is guaranteed that the unrounded shortest time will be no more than 0.4 away from the closest integer. Also, if you decide to use inverse trigonometric functions in your solution (hint, hint!), try atan2() rather than acos() or asin().
Input
The input test file will contain multiple test cases. Each test case will begin with a single line containing an integer R, the maximum distance between points that the robot is allowed to travel (where 10 ≤ R ≤ 1000), and an integer n, the number of points (where 2 ≤ n ≤ 20). The next n lines each contain 2 integer values; here, the ith line contains xi and yi (where −1000 ≤ xi, yi ≤ 1000). Each of the points is guaranteed to be unique. The end-of-file is denoted by a test case with R = n = −1.
Output
The output test file should contain a single line per test case indicating the shortest possible time in second (rounded to the nearest integer) required for the robot to travel from (x1, y1) to (xn, yn). If no trip is possible, print “impossible” instead.
Sample Input
10 2
0 0
7 0
10 3
0 0
7 0
14 5
10 3
0 0
7 0
14 10
-1 -1
Sample Output
7
71
impossible
Source
Stanford Local 2006
注意：下面這個(gè)代碼是Wrong Answer的代碼：
1
#include <queue>
2#include <stdio.h>
3#include <math.h>
4using namespace std;
5
6const int N = 21;
7const double EPS = 1e-8f;
8const double INF = 1e100;
9const double PI = acos(-1.0);
10
11inline int dblcmp(double a, double b) {
12 if(fabs(a-b) < EPS)
13 return 0;
14 return a < b ? -1 : 1;
15}
16
17int D, n;
18double x[N], y[N];
19double d[N];
20bool chk[N];
21
22struct Node {
23 double a;
24 int id;
25 Node(){}
26 Node(int ii, double aa) {
27 a = aa;
28 id = ii;
29 }
30};
31
32bool operator<(const Node& a, const Node& b) {
33 return dblcmp(d[a.id], d[b.id]) == 1;
34}
35
36double cal_dist(double agl, int a, int b, double& old) {
37 old = atan2(y[b]-y[a], x[b]-x[a]);
38 double now = fabs(old-agl);
39 double now2 = 2*PI-fabs(old-agl);
40 if(now2 < now) now = now2;
41 double dist = sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]) );
42 if(dblcmp(dist, D) == 1)
43 return INF;
44 return now * 180.0/PI + dist;
45}
46
47void solve() {
48 int i;
49 priority_queue<Node> PQ;
50 memset(chk, 0, sizeof(chk));
51 double a = atan2(y[n-1]-y[0], x[n-1]-x[0]);
52 PQ.push(Node(0, a));
53 d[0] = 0;
54 for(i = 1; i < n; ++i)
55 d[i] = INF;
56 while(!PQ.empty()) {
57 double a = PQ.top().a;
58 int id = PQ.top().id;
59 PQ.pop();
60 if(chk[id]) continue;
61 chk[id] = 1;
62 if(id == n-1) {
63 printf("%.0lf\n", d[n-1]);
64 return;
65 }
66 for(i = 0; i < n; ++i) if(!chk[i]) {
67 double nowa;
68 double nowd = cal_dist(a, id, i, nowa);
69 if(dblcmp(nowd+d[id], d[i]) == -1) {
70 d[i] = nowd+d[id];
71 PQ.push(Node(i, nowa));
72 }
73 }
74 }
75
76 printf("impossible\n");
77}
78
79int main() {
80
81 freopen("t.in", "r", stdin);
82// freopen("t.out", "w", stdout);
83
84 int i;
85 while(scanf("%d %d", &D, &n), !(D==-1 && n==-1)) {
86 for(i = 0; i < n; ++i)
87 scanf("%lf%lf", &x[i], &y[i]);
88 solve();
89 }
90 return 0;
91}
92
這個(gè)代碼哪里錯(cuò)了呢？
思來(lái)想去想到可能是出現(xiàn)了下面這種情況
一個(gè)狀態(tài)A進(jìn)入隊(duì)列
過(guò)了一會(huì)又一個(gè)狀態(tài)通過(guò)其他路徑到達(dá)A狀態(tài) 并且耗費(fèi)比前面一次少
這個(gè)代碼的做法是直接把其送入PQ，由于修改了d[A], 所以希望這個(gè)節(jié)點(diǎn)能夠浮上去（浮到正確的位置）。
但是Wrong Answer。
可能這個(gè)節(jié)點(diǎn)在向上浮的過(guò)程中遇到了前面這個(gè)A狀態(tài) 于是就不往上浮了。但其實(shí)前面那個(gè)狀態(tài)并沒(méi)有修正本身的位置，所以導(dǎo)致了新的狀態(tài)的位置出錯(cuò)。
所以還是改成了下面的代碼 AC
1#include <queue>
2#include <stdio.h>
3#include <math.h>
4using namespace std;
5const int N = 21;
6const double EPS = 1e-8f;
7const double INF = 1e100;
8const double PI = acos(-1.0);
9
inline int dblcmp(double a, double b) 
{
10
if(fabs(a-b) < EPS)
11 return 0;
12 return a < b ? -1 : 1;
13
}
14int D, n;
15double x[N], y[N];
16double d[N];
17bool chk[N];
18struct Node {
19 double a, dist;
20 int id;
21
Node(){}
22 Node(int ii, double aa, double dd) {
23 a = aa; id = ii; dist = dd;
24
}
25};
26bool operator<(const Node& a, const Node& b) {
27 if(dblcmp(a.dist, b.dist) == 1)
28 return true;
29 return false;
30}
31double cal_dist(double agl, int a, int b, double& old) {
32 old = atan2(y[b]-y[a], x[b]-x[a]);
33 double now = fabs(old-agl);
34 double now2 = 2*PI-fabs(old-agl);
35 if(now2 < now) now = now2;
36 double dist = sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]) );
37 if(dblcmp(dist, D) == 1)
38 return INF;
39 return now * 180.0/PI + dist;
40}
41void solve() {
42 int i;
43 priority_queue<Node> PQ;
44 memset(chk, 0, sizeof(chk));
45 double a = atan2(y[n-1]-y[0], x[n-1]-x[0]);
46 PQ.push(Node(0, a, 0));
47 d[0] = 0;
48 for(i = 1; i < n; ++i)
49 d[i] = INF;
50 while(!PQ.empty()) {
51 double a = PQ.top().a;
52 int id = PQ.top().id;
53 double dist = PQ.top().dist;
54 PQ.pop();
55 if(chk[id]) continue;
56 chk[id] = 1;
57 if(id == n-1) {
58 printf("%.0lf\n", d[n-1]);
59 return;
60 }
61 for(i = 0; i < n; ++i) if(!chk[i]) {
62 double nowa;
63 double nowd = cal_dist(a, id, i, nowa);
64 if(dblcmp(nowd+d[id], d[i]) == -1) {
65 d[i] = nowd+d[id];
66 PQ.push(Node(i, nowa, nowd+d[id]));
67 }
68 }
69 }
70 printf("impossible\n");
71}
72int main() {
73 freopen("t.in", "r", stdin);
74 int i;
75 while(scanf("%d %d", &D, &n), !(D==-1 && n==-1)) {
76 for(i = 0; i < n; ++i)
77 scanf("%lf%lf", &x[i], &y[i]);
78 solve();
79 }
80 return 0;
81}
82