POJ-2632

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