ZOJ 2803 Crashing Robots

于 2011年01月11日 发布在 算法&&ACM 跳到评论

ZOJ 2803 Crashing Robots

“机器人模拟,给定一个A*B的地图,给定N个机器人的初始位置和方向,然后会有M个操作,判断这M是否能正常执行,如果能,输出“OK”,否则输出是出界还是与另外的机器人相撞。操作是一步一步执行的,没有两个同时发生,’R’,’L’,’F’分别表示向右转,向左转,向前进一步……”

步骤比较繁,但是没有什么陷阱,考耐心。此题麻烦的就是方向的转化,用一个dir数组保存方向的变化量,然后每个方向对应一个变化量。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct robot
{
    int x,y;
    char dir;
};//机器人的属性
struct info
{
    int from,to;
}stopinfo;//当停止执行操作的时候的信息,比如说from撞到了to

int dir[4][2] = {0,1,0,-1,1,0,-1,0};
int getdir(char c)
{
    switch( c )
    {
        case 'N':return 0;
        case 'W':return 3;  //每个方向对应了一个坐标增量
        case 'E':return 2;
        case 'S':return 1;
    }
    return 0;
}

int mat[101][101];
int n,m;
struct robot robots[101];
char dirtemp[5],order[5],c;
int R,repeat;

int main(void)
{
    int cases,i,j,over,
    int x,y,d,xx,yy;
    int Nrobots,Ninstru;
    scanf("%d",&cases);
    while( cases-- )
    {
        scanf("%d%d",&n,&m);
        scanf("%d%d",&Nrobots,&Ninstru);  //Nrobots机器人个数,Ninstru操作的个数

        memset( mat,0,sizeof(mat) );

        for( i = 1; i <= Nrobots; i++ )
        {
            scanf("%d%d%s",&x,&y,dirtemp);
            mat[x][y] = i;
            robots[i].x = x;
            robots[i].y = y;
            robots[i].dir = dirtemp[0];
        }//录入机器人的信息,坐标,方向

        over = 0;
        for( i = 1; i <= Ninstru; i++ )
        {
            scanf("%d%s%d",&R,order,&repeat);
            while( repeat-- )
            {
                if( order[0] == 'R' )
                {
                    switch( robots[R].dir )//转换方向
                    {
                        case 'N':robots[R].dir = 'E';break;
                        case 'W':robots[R].dir = 'N';break;
                        case 'E':robots[R].dir = 'S';break;
                        case 'S':robots[R].dir = 'W';break;
                    }
                }
                else if( order[0] == 'L' )
                {
                    switch( robots[R].dir )
                    {
                        case 'N':robots[R].dir = 'W';break;
                        case 'W':robots[R].dir = 'S';break;
                        case 'E':robots[R].dir = 'N';break;
                        case 'S':robots[R].dir = 'E';break;
                    }
                }
                else if( order[0] == 'F' )
                {
                    d = getdir( robots[R].dir );  //对于坐标增量,判断下一时刻的坐标
                    xx = robots[R].x + dir[d][0];
                    yy = robots[R].y + dir[d][1];

                    if( xx < 1 || yy < 1 || xx > n || yy > m )  //超出范围是撞墙了,over = 1
                        {over = 1;stopinfo.from = R;break;}
                    if( mat[xx][yy] ) //这个是跟机器人撞了
                    {
                        over = 2;
                        stopinfo.from = R;
                        stopinfo.to = mat[xx][yy];
                        break;
                    }

                    mat[ robots[R].x ][ robots[R].y ] = 0;//对mat地图进行更新
                    mat[xx][yy] = R;
                    robots[R].x = xx;
                    robots[R].y = yy;
                }
            }
            if( over ) break;
        }

        for( i++; i <= Ninstru; i++ )
            scanf("%d%s%d",&R,order,&repeat);

        if( over == 1 )
            printf("Robot %d crashes into the wall\n",stopinfo.from);
        else if( over == 2 )
            printf("Robot %d crashes into robot %d\n",stopinfo.from,stopinfo.to);
        else
            printf("OK\n");
    }
    return 0;
}

本文共有 3条评论 | 沙发:文章评论

  1. 站长工具说道:

    博主的文章很不错,我是站长工具-站长精灵的作者,一款专业的SEO工具软件(可以帮您提高博客的流量),想跟您交换个链接,不知可否

  2. 小媛说道:

    你的页面应该再宽点下面的表情挺难看的

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)