本文共 1788 字，大约阅读时间需要 5 分钟。
1 /* 2 题意；从原点出发，四个方向，碰到一个点向右转，问多少次才能走出，若不能输出-1 3 模拟：碰到的点横坐标相等或纵坐标相等，然而要先满足碰到点最近， 4 当没有转向或走到之前走过的点结束循环。dir数组使得代码精简巧妙 5 对点离原点排序竟然submit failed，别人的代码有毒！ 6 */ 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std;13 14 const int MAXN = 1e3 + 10;15 const int INF = 0x3f3f3f3f;16 int x[MAXN], y[MAXN];17 int dir[4][2] = { 1, 0, 0, -1, -1, 0, 0, 1};18 int n;19 int vis[4][MAXN];20 21 int work(void)22 {23 int nx = 0, ny = 0; int d = 0; int res = 0;24 memset (vis, 0, sizeof (vis));25 26 while (true)27 {28 int mx = INF, p = -1;29 for (int i=1; i<=n; ++i)30 {31 if (d == 0 || d == 2)32 {33 if (ny != y[i]) continue;34 if ((x[i] - nx) * dir[d][0] < 0) continue;35 }36 else37 {38 if (nx != x[i]) continue;39 if ((y[i] - ny) * dir[d][1] < 0) continue;40 }41 42 int tmp = abs (x[i] - nx) + abs (y[i] - ny);43 if (tmp < mx) {mx = tmp; p = i;}44 }45 46 if (p == -1) return res;47 if (vis[d][p]) return -1;48 vis[d][p] = 1;49 nx = x[p] - dir[d][0]; ny = y[p] - dir[d][1];50 d = (d + 1) % 4; res++;51 }52 53 }54 55 int main(void) //SCU 4445 Right turn56 {57 // freopen ("E.in", "r", stdin);58 59 while (scanf ("%d", &n) == 1)60 {61 for (int i=1; i<=n; ++i)62 {63 scanf ("%d%d", &x[i], &y[i]);64 }65 printf ("%d\n", work ());66 }67 68 return 0;69 }
转载于:https://www.cnblogs.com/Running-Time/p/4644692.html