POJ2632
1.题目大意：在一个a×b的仓库里有n个机器人，编号为1到n。现在给出每一个机器人的坐标和它所面朝的方向，以及m条指令，每条指令由三部分组成：整数num代表该条指令调用的机器人的编号；字符act表示操作：其中L表示原地向左转90°，R表示原地向右转90°，F表示向前走一步；整数rep表示执行该条指令的次数。已知，当两个机器人坐标相同时他们会相撞，某一个机器人走出仓库也会撞到墙，问你能否安全执行这m条指令，如果能则输出“OK”；否则输出中断原因（哪两个机器人相撞，或是哪个机器人撞到墙了）。
2.注意点：
A is the length in the EW-direction, and B in the NS-direction.
坐标系要改变为二维矩阵的形式，N、W、S、E的方向变化必须注意：改变坐标系后，N为南，S为北，WE不变，L转右，R转左，F不变
3.技巧：关于描述机器人的转弯，这里用到了一个技巧。
int dir[4][2]={
{1,0},{0,1},{-1,0},{0,-1}};
...
if(ch=='E') r[i].dir=0;
if(ch=='N') r[i].dir=1;
if(ch=='W') r[i].dir=2;
if(ch=='S') r[i].dir=3;
...
if(act[i]=='R') //左转弯
while(rep[i]--)
{
int mov=r[num[i]].dir-1;
if(mov==-1) mov=3;
r[num[i]].dir=mov;
}
/*假设原来的方向面朝S（这里S是北），向左转，则int mov=r[num[i].dir]-1;所以此时的方向3-1=2，也就是r[num[i]].dir=2;此时向西，符合要求。
下一次再用这个机器人时，新的x,y是：
x=r[num[i]].x+dir[r[num[i]].dir][0];y=r[num[i]].y+dir[r[num[i]].dir][1];
而r[num[i].dir]=2.此时我们看dir[4][2]中的dir[2][0]恰好是
-1，dir[2][1]恰好是0，表明此时向西运动，符合要求。*/模拟：
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef struct node
{int x,y,dir;
}robit;
robit r[110];
bool s[110][110]; //用s二维数组判断这个格子上有没有robot
int dir[4][2]={
{
1,0},{
0,1},{-1,0},{
0,-1}};
int a,b,n,m;
int num[110],rep[110];
char act[110];
bool judge(int x,int y)
{if(x<1||x>a||y<1||y>b)return true;return false;
}
void solve()
{int x,y;for(int i=1;i<=m;i++){bool flag=true;if(act[i]=='F'){s[r[num[i]].x][r[num[i]].y]=false;while(rep[i]--){x=r[num[i]].x+dir[r[num[i]].dir][0];y=r[num[i]].y+dir[r[num[i]].dir][1];if(judge(x,y)){printf("Robot %d crashes into the wall\n",num[i]);flag=false;break;}if(s[x][y]){int k;for(k=1;k<=n;k++)if(r[k].x==x&&r[k].y==y) break;printf("Robot %d crashes into robot %d\n",num[i],k);flag=false;break;}r[num[i]].x=x;r[num[i]].y=y;r[num[i]].dir=r[num[i]].dir;}s[x][y]=true;}rep[i]%=4;if(act[i]=='R')while(rep[i]--){int mov=r[num[i]].dir-1;if(mov==-1) mov=3;r[num[i]].dir=mov;}if(act[i]=='L')while(rep[i]--){int mov=r[num[i]].dir+1;if(mov==4) mov=0;r[num[i]].dir=mov;}if(!flag) break;if(i==m) printf("OK\n");}
}
int main()
{int t;scanf("%d",&t);while(t--){char ch;memset(s,0,sizeof(s));scanf("%d%d",&a,&b);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){cin>>r[i].x>>r[i].y>>ch;s[r[i].x][r[i].y]=true;if(ch=='E') r[i].dir=0;if(ch=='N') r[i].dir=1;if(ch=='W') r[i].dir=2;if(ch=='S') r[i].dir=3;}for(int i=1;i<=m;i++)cin>>num[i]>>act[i]>>rep[i];solve();}return 0;
}
——————————————————————————————————————————————————————
没有用dir统一方向，写起来很麻烦。
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int main(){int cases;int a,b; //a列数,b行数int n,m;//n机器人数,m指令数int x,y; //机器人坐标char dir; //机器人方向int rob[101],rep[101];char act[101];bool flag=false;int i,k;int post[110][110]; //记录机器人初始方向int num[110][110]; //机器人的编号int xx[101],yy[110]; //机器人编号cin>>cases;while(cases--){memset(post,-1,sizeof(post));memset(num,0,sizeof(num));memset(xx,0,sizeof(xx));memset(yy,0,sizeof(yy));cin>>a>>b;cin>>n>>m;for(int i=1;i<=n;i++){cin>>y>>x>>dir;xx[i]=x;yy[i]=y;num[x][y]=i;//由于坐标系的改变，上下颠倒，N是南，S是北，WE不变if(dir=='S') post[x][y]=0; //0 or 360else if(dir=='E') post[x][y]=1; //90else if(dir=='N') post[x][y]=2; //180else if(dir=='W') post[x][y]=3; //270}/*input <robot #>< action>< repeat>*/for(k=1;k<=m;k++)cin>>rob[k]>>act[k]>>rep[k];bool flag=false;int row,col;for(k=1;k<=m;k++){row=xx[rob[k]];col=yy[rob[k]];if(act[k]=='L'){ //由于坐标系改变，转向相反，L向右转，R左转rep[k]%=4; //角度每转4次（360）回到原位post[row][col]=(post[row][col]+rep[k])%4;}else if(act[k]=='R'){rep[k]%=4;post[row][col]=(post[row][col]-rep[k])%4;if(post[row][col]<0) post[row][col]+=4;}else if(act[k]=='F'){if(post[row][col]==0) //N方向判断for(i=1;i<rep[k];i++){if(num[row-i][col]){ //如果该格存在编号（另外的机器人）cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row-i][col];flag=true;break;}if(row-i<1){ //判断是否撞墙cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;flag=true;break;}if(i==rep[k]){//移动中没有任何碰撞，则更新robot的坐标post[row][col]=-1; //原坐标方向重置num[row][col]=0; //原坐标编号重置row-=rep[k];xx[rob[k]]-=rep[k];post[row][col]=0; //新坐标方向更新num[row][col]=rob[k]; //新坐标编号更新}}else if(post[row][col]==1) //E方向移动判断for(i=1;i<=rep[k];i++){if(num[row][col+i]){cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row][col+i]<<endl;flag=true;break;}if(col+i>a){cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;flag=true;break;}if(i==rep[k]){post[row][col]=-1;num[row][col]=0;col+=rep[k];yy[rob[k]]+=rep[k];post[row][col]=1;num[row][col]=rob[k];}}else if(post[row][col]==2) //S方向移动判断for(i=1;i<=rep[k];i++){if(num[row+i][col]){cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row+i][col]<<endl;flag=true;break;}if(row+i>b){cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;flag=true;break;}if(i==rep[k]){post[row][col]=-1;num[row][col]=0;row+=rep[k];xx[rob[k]]+=rep[k];post[row][col]=2;num[row][col]=rob[k];}}else if(post[row][col]==3) //W方向移动判断for(i=1;i<=rep[k];i++){if(num[row][col-i]){cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row][col-i]<<endl;flag=true;break;}if(col-i<1){cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;flag=true;break;}if(i==rep[k]){post[row][col]=-1;num[row][col]=0;col-=rep[k];yy[rob[k]]-=rep[k];post[row][col]=3;num[row][col]=rob[k];}}}if(flag)break;}if(!flag)cout<<"OK"<<endl; }return 0;
}