首页 > 代码库 > poj 2632 Crashing Robots(模拟)

poj 2632 Crashing Robots(模拟)

链接:poj 2632

题意:在n*m的房间有num个机器,它们的坐标和方向已知,现给定一些指令及机器k执行的次数,

L代表机器方向向左旋转90°,R代表机器方向向右旋转90°,F表示前进,每次前进一米

若前进时机器i撞到机器j,输出“Robot i crashes into robot j ”

若机器走出了n*m的房间,输出“Robot i crashes into the wall ”

当出现上述情况,只需输出第一次出现上述的情况

若所有指令执行完,所有机器都没碰到上述情况,输出“OK”

思路:理解题意后,简单模拟就可以了

注意:行和列要分清,题中都是先输入列,还要注意机器的方向

#include<stdio.h>
#include<string.h>
int x[4]={1,0,-1,0},y[4]={0,1,0,-1};  //北东南西
int num,m,n,vis[101][101];
struct stu
{
    int r,c,dir;
}rob[105];
int rob_go(int k,char c,int time)
{
    int i,ri,ci;
    if(c=='L'){
        time%=4;
        rob[k].dir=(rob[k].dir+4-time)%4;
    }
    else if(c=='R'){
        time%=4;
        rob[k].dir=(rob[k].dir+time)%4;
    }
    else if(c=='F'){
        ri=rob[k].r;
        ci=rob[k].c;
        vis[ri][ci]=0;
        while(time--){
            ri+=x[rob[k].dir];
            ci+=y[rob[k].dir];
            if(vis[ri][ci]){ //若撞到某机器,返回该机器的编号
                for(i=1;i<=num;i++)
                    if(ri==rob[i].r&&ci==rob[i].c)  
                        return i;
            }
        }
        if(ri<1||ri>n||ci<1||ci>m)
            return -1;         //用-1标记机器走到了墙里
        rob[k].r=ri;
        rob[k].c=ci;
        vis[ri][ci]=1;
    }
    return 0;
}
int main()
{
    int T,i,ins,flag,k,time;
    char c;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d",&m,&n,&num,&ins);
        memset(vis,0,sizeof(vis));          //标记此处机器是否存在,0代表不存在
        for(i=1;i<=num;i++){
            scanf("%d %d %c",&rob[i].c,&rob[i].r,&c);
            vis[rob[i].r][rob[i].c]=1;      //1表示此处有机器
            if(c=='N')
                rob[i].dir=0;
            else if(c=='E')
                rob[i].dir=1;
            else if(c=='S')
                rob[i].dir=2;
            else if(c=='W')
                rob[i].dir=3;
        }
        flag=0;
        i=0;
        while(ins--){
            scanf("%d %c %d",&k,&c,&time);
            if(!flag){
                flag=rob_go(k,c,time);
                if(flag&&!i)  //若撞到其他机器或走到墙里,其他就不必判断了
                    i=k;      //记录第一次未安全执行完指令的机器
            }
        }
        if(flag==0)
            printf("OK\n");
        else if(flag==-1)
            printf("Robot %d crashes into the wall\n",i);
        else
            printf("Robot %d crashes into robot %d\n",i,flag);
    }
    return 0;
}


poj 2632 Crashing Robots(模拟)