In a modernized warehouse, robots are used to fetch the goods. Careful planning is needed to ensure that the robots reach their destinations without crashing into each other. Of course, all warehouses are rectangular, and all robots occupy a circular floor space with a diameter of 1 meter. Assume there are N robots, numbered from 1 through N. You will get to know the position and orientation of each robot, and all the instructions, which are carefully (and mindlessly) followed by the robots. Instructions are processed in the order they come. No two robots move simultaneously; a robot always completes its move before the next one starts moving.
A robot crashes with a wall if it attempts to move outside the area of the warehouse, and two robots crash with each other if they ever try to occupy the same spot.
A robot crashes with a wall if it attempts to move outside the area of the warehouse, and two robots crash with each other if they ever try to occupy the same spot.
Input
The first line of input is K, the number of test cases. Each test case starts with one line consisting of two integers, 1 <= A, B <= 100, giving the size of the warehouse in meters. A is the length in the EW-direction, and B in the NS-direction.
The second line contains two integers, 1 <= N, M <= 100, denoting the numbers of robots and instructions respectively.
Then follow N lines with two integers, 1 <= Xi <= A, 1 <= Yi <= B and one letter (N, S, E or W), giving the starting position and direction of each robot, in order from 1 through N. No two robots start at the same position.
Figure 1: The starting positions of the robots in the sample warehouse
Finally there are M lines, giving the instructions in sequential order.
An instruction has the following format:
< robot #> < action> < repeat>
Where is one of
and 1 <= < repeat> <= 100 is the number of times the robot should perform this single move.
The second line contains two integers, 1 <= N, M <= 100, denoting the numbers of robots and instructions respectively.
Then follow N lines with two integers, 1 <= Xi <= A, 1 <= Yi <= B and one letter (N, S, E or W), giving the starting position and direction of each robot, in order from 1 through N. No two robots start at the same position.
Figure 1: The starting positions of the robots in the sample warehouse
Finally there are M lines, giving the instructions in sequential order.
An instruction has the following format:
< robot #> < action> < repeat>
Where is one of
- L: turn left 90 degrees,
- R: turn right 90 degrees, or
- F: move forward one meter,
and 1 <= < repeat> <= 100 is the number of times the robot should perform this single move.
Output
Output one line for each test case:
Only the first crash is to be reported.
- Robot i crashes into the wall, if robot i crashes into a wall. (A robot crashes into a wall if Xi = 0, Xi = A + 1, Yi = 0 or Yi = B + 1.)
- Robot i crashes into robot j, if robots i and j crash, and i is the moving robot.
- OK, if no crashing occurs.
Only the first crash is to be reported.
Sample Input
4 5 4 2 2 1 1 E 5 4 W 1 F 7 2 F 7 5 4 2 4 1 1 E 5 4 W 1 F 3 2 F 1 1 L 1 1 F 3 5 4 2 2 1 1 E 5 4 W 1 L 96 1 F 2 5 4 2 3 1 1 E 5 4 W 1 F 4 1 L 1 1 F 20
Sample Output
Robot 1 crashes into the wall Robot 1 crashes into robot 2 OK Robot 1 crashes into robot 2
思路：
直接暴力模拟这些操作。
ps:写的时候没想太多，直接强行模拟，结果发现有的地方写错了，强行改回来最后发现把代码改得巨丑无比，心态炸了。还好ac了，要不实在没法改了。
代码：
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<map> #include<queue> #include<stack> #include<set> #include<list> using namespace std; #define ll long long const int Mod = 1e9+7; const int inf = 1e9; const int Max = 1e5+10; vector<int>vt[Max]; //void exgcd(ll a,ll b,ll& d,ll& x,ll& y){if(!b){d=a;x=1;y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}} //ll inv(ll a,ll n){ll d, x, y;exgcd(a,n,d,x,y);return (x+n)%n;} ��Ԫ //int gcd(int a,int b) { return (b>0)?gcd(b,a%b):a; } ��С��Լ //int lcm(int a, int b) { return a*b/gcd(a, b); } ��С���� int fun1(char c){ if(c == 'N') return 0; if(c == 'E') return 1; if(c == 'S') return 2; if(c == 'W') return 3; } int main() { int t,l,r,n,m,k[110],cnt[110],i,j,mp[110][110],x[110],y[110],v[110]; char p[110],z; cin>>t; while(t--){ int ans1=0,ans2=0,ans3=0,flag=0; memset(mp,0,sizeof(mp)); memset(v,0,sizeof(v)); cin>>l>>r; cin>>n>>m; for(i=1;i<=n;i++){ cin>>x[i]>>y[i]>>z; mp[x[i]][y[i]] = i; v[i] = fun1(z); } for(i=1;i<=m;i++) cin>>k[i]>>p[i]>>cnt[i]; for(i=1;i<=m;i++){ if(p[i]=='L'){ v[k[i]] -= cnt[i]; while(v[k[i]]<0) v[k[i]] += 4; } if(p[i]=='R'){ v[k[i]] += cnt[i]; v[k[i]] %= 4; } if(p[i]=='F'){ if(v[k[i]]==0){ for(j=1;j<=cnt[i];j++){ if(mp[x[k[i]]][y[k[i]]+j]!=0){ ans1 = k[i];ans2 = mp[x[k[i]]][y[k[i]]+j]; flag = 1; break; } if(y[k[i]]+j>r){ flag = 2; ans3 = k[i];break; } } if(flag==0){ mp[x[k[i]]][y[k[i]]+cnt[i]] = k[i]; mp[x[k[i]]][y[k[i]]] = 0; y[k[i]] += cnt[i]; } } if(v[k[i]]==1){ for(j=1;j<=cnt[i];j++){ if(mp[x[k[i]]+j][y[k[i]]]!=0){ ans1 = k[i];ans2 = mp[x[k[i]]+j][y[k[i]]]; flag = 1; break; } if(x[k[i]]+j>l){ flag = 2; ans3 = k[i];break; } } if(flag==0){ mp[x[k[i]]+cnt[i]][y[k[i]]] = k[i]; mp[x[k[i]]][y[k[i]]] = 0; x[k[i]] += cnt[i]; } } if(v[k[i]]==2){ for(j=1;j<=cnt[i];j++){ if(mp[x[k[i]]][y[k[i]]-j]!=0){ ans1 = k[i];ans2 = mp[x[k[i]]][y[k[i]]-j]; flag = 1; break; } if(y[k[i]]-j<=0){ flag = 2; ans3 = k[i];break; } } if(flag==0){ mp[x[k[i]]][y[k[i]]-cnt[i]] = k[i]; mp[x[k[i]]][y[k[i]]] = 0; y[k[i]] -= cnt[i]; } } if(v[k[i]]==3){ for(j=1;j<=cnt[i];j++){ if(mp[x[k[i]]-j][y[k[i]]]!=0){ ans1 = k[i];ans2 = mp[x[k[i]]-j][y[k[i]]]; flag = 1; break; } if(x[k[i]]-j<=0){ flag = 2; ans3 = k[i];break; } } if(flag==0){ mp[x[k[i]]-cnt[i]][y[k[i]]] = k[i]; mp[x[k[i]]][y[k[i]]] = 0; x[k[i]] -= cnt[i]; } } } if(flag!=0) break; } if(flag == 0) cout<<"OK"<<endl; else if(flag == 1) cout<<"Robot "<<ans1<<" crashes into robot "<<ans2<<endl; else if(flag == 2) cout<<"Robot "<<ans3<<" crashes into the wall"<<endl; } return 0; }
打完后看了下室友的代码，越发觉得自己是个智障了。。。。
室友代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<stack> #include<map> #include<vector> #include<set> using namespace std; const int MAX=1e2+10; const double eps=1e-6; #define INF 0x7fffffff #define ll long long #define FOR(i,a,b) for(int i=a;i<=b;i++) #define ROF(i,a,b) for(int i=a;i>=b;i--) #define mst(a) memset(a,0,sizeof(a)) #define mstn(a,n) memset(a,n,sizeof(a)) struct num{int x,y,fac;}a[MAX]; //bool cmp(const num &x, const num &y){return x.l==y.l?x.r<y.r:x.l<y.l;} int flag,mx,my,n,m; void wrong(int x,int y,int i) { if(x==0||x==mx+1||y==0||y==my+1) printf("Robot %d crashes into the wall ",i),flag=0; else { int d=0; FOR(j,1,n) { if(j==i) continue; else if(a[j].x==x&&a[j].y==y) d=j; } if(d) { printf("Robot %d crashes into robot %d ",i,d); flag=0; } } } void turn(int i,char ch,int t) { if(!flag) return; if(ch=='L') a[i].fac=(a[i].fac-t%4+4)%4; else if(ch=='R') a[i].fac=(a[i].fac+t%4)%4; else while(t--) { if(a[i].fac==0) a[i].y++; if(a[i].fac==1) a[i].x++; if(a[i].fac==2) a[i].y--; if(a[i].fac==3) a[i].x--; wrong(a[i].x,a[i].y,i); if(!flag) break; } } int main() { int T,x,y; char ch; cin>>T; while(T--) { cin>>mx>>my; flag=1; cin>>n>>m; FOR(i,1,n) { cin>>x>>y>>ch; a[i].x=x,a[i].y=y; if(ch=='N') a[i].fac=0; if(ch=='E') a[i].fac=1; if(ch=='S') a[i].fac=2; if(ch=='W') a[i].fac=3; } FOR(i,1,m) { int num,t; cin>>num>>ch>>t; if(flag) turn(num,ch,t); } if(flag) cout<<"OK"<<endl; } return 0; }
耗时都是16ms,但空间复杂度和可读性差很多啊。。。