#include<stdio.h>
int main()
{
int k,a,b,n,m,i,j,num,rep,rect[100][100],robot[100][3];
int flag;
char c;
for(scanf("%d",&k);k>0;k--)
{
scanf("%d%d%d%d",&a,&b,&n,&m);
for(i=0;i<b;i++)
for(j=0;j<a;j++) rect[i][j]=0;
for(i=0;i<n;i++)
{
scanf("%d %d %c",&robot[i][1],&robot[i][0],&c);
robot[i][0]--; robot[i][1]--;
switch(c)
{
case 'N':robot[i][2]=0; break;
case 'W':robot[i][2]=1; break;
case 'S':robot[i][2]=2; break;
case 'E':robot[i][2]=3; break;
}
rect[robot[i][0]][robot[i][1]]=i+1;
}
flag=1;
for(i=0;i<m;i++)
{
scanf("%d %c %d",&num,&c,&rep); num--;
for(;rep>0;rep--)
{
if (flag){
if (c=='L') robot[num][2]=(robot[num][2]+1)%4;
if (c=='R') robot[num][2]=(robot[num][2]-1);
if (robot[num][2]<0) robot[num][2]+=4;
if (robot[num][2]<0) robot[num][2]=-robot[num][2];
if (c=='F')
switch(robot[num][2])
{
case 0:
rect[robot[num][0]][robot[num][1]]=0;
robot[num][0]++;
rect[robot[num][0]][robot[num][1]]+=(num+1);
break;
case 1:
rect[robot[num][0]][robot[num][1]]=0;
robot[num][1]--;
rect[robot[num][0]][robot[num][1]]+=(num+1);
break;
case 2:
rect[robot[num][0]][robot[num][1]]=0;
robot[num][0]--;
rect[robot[num][0]][robot[num][1]]+=(num+1);
break;
case 3:
rect[robot[num][0]][robot[num][1]]=0;
robot[num][1]++;
rect[robot[num][0]][robot[num][1]]+=(num+1);
break;
}
if (robot[num][0]<0||robot[num][0]>=b||robot[num][1]<0||robot[num][1]>=a)
{
printf("Robot %d crashes into the walln",num+1);
flag=0;
}
if (rect[robot[num][0]][robot[num][1]]>(num+1))
{
printf("Robot %d crashes into robot %dn",num+1,rect[robot[num][0]][robot[num][1]]-num-1);
flag=0;
}}
}
}
if (flag) printf("OKn");
}
system("pause");
return 0;
}
题意简述
给定A*B的格子，放入N个机器人，每个机器人初始位置及朝向给定。给定M条指令。指令类型有三种：
1、L：左转90° 2、R：右转90° 3、F：前进一格
问执行指令过程中机器人是否发生碰撞，碰撞包括碰墙或碰其他机器人。安全执行完所有指令输出OK。（程序只需输出发生的第一次碰撞）
算法分析
模拟法。一条一条指令执行。指令执行过程把一条指令重复几遍拆分成几条指令来执行。每执行一条判断是否发生碰撞。若发生碰撞则标记位记0并输出。注意还需继续读取剩余输入。
Problem Status: AC。时间0ms，内存156k
——————————————————————分割线——————————————————————
TIPS：
机器人方向用0~3 四个数字表示四个朝向。转向时自增或自减即可。注意处理转后方向变为负值的情况。
——————————————————————分割线——————————————————————
优化：
POJ最高成绩：内存4k 时间0ms……我现在开始怀疑内存占用和编译器有关系了……太诡异了……
