POJ-2632 解题报告

题意简述

给定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……我现在开始怀疑内存占用和编译器有关系了……太诡异了……

程序样例

[c]#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;
}
[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *