模拟 POJ 2632 Crashing Robots

  1 /*
  2     题意：几个机器人按照指示，逐个朝某个(指定)方向的直走，如果走过的路上有机器人则输出谁撞到；如果走出界了，输出谁出界
  3             如果以上都没发生，则输出OK
  4     模拟题：无算法，按照条件编写几个函数和判断条件
  5     注意：1. 关于绕转，只要模拟人的转圈方向，比如向右转就向右手边转(优化：当超过4次则对4取模)
  6             2. 有先撞墙还是先撞机器人的问题(每一次‘F‘后都要及时判断是否OK)
  7             3. 撞哪个机器人也有先来后到的顺序(‘F‘后以这个机器人(除自己以外)遍历一边是否OK)
  8 */
  9 #include <cstdio>
 10 #include <iostream>
 11 #include <algorithm>
 12 #include <cstring>
 13 #include <cmath>
 14 #include <string>
 15 #include <map>
 16 #include <queue>
 17 #include <vector>
 18 using namespace std;
 19 
 20 const int MAXN = 1e6 + 10;
 21 const int INF = 0x3f3f3f3f;
 22 struct NODE
 23 {
 24     int x, y;
 25     int dir;
 26 }node[MAXN];
 27 struct OP
 28 {
 29     int name, t;
 30     char move;
 31 }op[MAXN];
 32 bool flag;
 33 
 34 bool ok(int k, int N, int M, int n)
 35 {
 36     for (int i=1; i<=n; ++i)
 37     {
 38         if (node[i].x < 1 || node[i].x > N || node[i].y < 1 || node[i].y > M)
 39         {
 40             printf ("Robot %d crashes into the wall\n", i);
 41             flag = false;
 42             return false;
 43         }
 44     }
 45 
 46     for (int j=1; j<=n; ++j)
 47     {
 48         if (k != j && node[k].x == node[j].x && node[k].y == node[j].y)
 49         {
 50             printf ("Robot %d crashes into robot %d\n", k, j);
 51             flag = false;
 52             return false;
 53         }
 54     }
 55 
 56     flag = true;
 57     return true;
 58 }
 59 
 60 void forward(NODE *a, OP b, int N, int M, int n)
 61 {
 62     while (b.t--)
 63     {
 64         if (a->dir == ‘N‘)    a->x -= 1;
 65         else if (a->dir == ‘S‘)    a->x += 1;
 66         else if (a->dir == ‘W‘)    a->y -= 1;
 67         else    a->y += 1;
 68         if (!ok (b.name, N, M, n))    break; 
 69     }
 70 }
 71 
 72 NODE turn_l(NODE a, OP b)
 73 {
 74     b.t = (b.t >= 4) ? (b.t % 4) : b.t;
 75     while (b.t--)
 76     {
 77         if (a.dir == ‘N‘)    a.dir = ‘W‘;
 78         else if (a.dir == ‘S‘)    a.dir = ‘E‘;
 79         else if (a.dir == ‘E‘)    a.dir = ‘N‘;
 80         else    a.dir = ‘S‘;
 81     }
 82 
 83     return a;
 84 }
 85 
 86 NODE turn_r(NODE a, OP b)
 87 {
 88     b.t = (b.t >= 4) ? (b.t % 4) : b.t;
 89     while (b.t--)
 90     {
 91         if (a.dir == ‘N‘)    a.dir = ‘E‘;
 92         else if (a.dir == ‘S‘)    a.dir = ‘W‘;
 93         else if (a.dir == ‘W‘)    a.dir = ‘N‘;
 94         else    a.dir = ‘S‘;
 95     }
 96 
 97     return a;
 98 }
 99 
100 void work(int N, int M, int n, int m)
101 {
102     int i;
103     for (i=1; i<=m; ++i)
104     {
105         if (op[i].move == ‘F‘)
106             forward (&node[op[i].name], op[i], N, M, n);
107         else if (op[i].move == ‘L‘)
108             node[op[i].name] = turn_l (node[op[i].name], op[i]);
109         else if (op[i].move == ‘R‘)
110             node[op[i].name] = turn_r (node[op[i].name], op[i]);
111         if (flag)    continue;
112         else    break;
113     }
114     if (i == m + 1)        puts ("OK");
115 }
116 
117 int main(void)        //POJ 2632 Crashing Robots
118 {
119     //freopen ("G.in", "r", stdin);
120 
121     int t;
122     scanf ("%d", &t);
123     while (t--)
124     {
125         int N, M, n, m;
126         scanf ("%d%d", &M, &N);
127         scanf ("%d%d", &n, &m);
128         for (int i=1; i<=n; ++i)
129         {
130             scanf ("%d %d %c", &node[i].y, &node[i].x, &node[i].dir);
131             node[i].x = N + 1 - node[i].x;
132         }
133         for (int i=1; i<=m; ++i)
134         {
135             scanf ("%d %c %d", &op[i].name, &op[i].move, &op[i].t);
136         }
137 
138         flag = true;
139         work (N, M, n, m);
140     }
141 
142     return 0;
143 }
144 
145 /*
146 Robot 1 crashes into the wall
147 Robot 1 crashes into robot 2
148 OK
149 Robot 1 crashes into robot 2
150 */