Chinaunix首页 | 论坛 | 博客
  • 博客访问: 474251
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类:

2009-10-08 18:58:57

解题思路

题意:

一个矩形,分成了A*B个大小相同的正方形,把n个机器人放在某些小正方形里,给他们一些指令,他们会一步一步按指令行动,每次只有一个机器人行动。如果两个机器人在同一个小正方形里了他们会相撞;如果出界了,会撞到墙。输出做一些指令之后机器人的第一次相撞的状态。

 

思路:

       直接模拟,记录n个机器人的位置跟方向,然后按照指令一步一步行动,方向可用四个数字表示。

源程序

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 103
struct position
{    
    int x; //横的
    int y; //竖的
    int dir; //东南西北依次为1234
}pos[N];
int t, n, m, A, B;
int f(char c)
{
    switch(c)
    {
    case'E': return 1;
    case'S': return 2;
    case'W': return 3;
    case'N': return 4;
    }
}
int mark[N];
int isexit(struct position r)
{
    int i;
    for(i=1; i<=n; i++)
    {
        if(! mark[i] && r.x == pos[i].x && r.y == pos[i].y)
            return i;
    }
    return 0;
}

int isout(struct position r)
{
    if(r.x <= 0 || r.x > A || r.y <=0 || r.y > B)
        return 1;
    else return 0;
}

int main()
{
    int i, j, k, bad;
    int a, b;

    char c;
    freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d%d", &A, &B, &n, &m);
        memset(pos, 0, sizeof(pos));
        for(i=1; i<=n; i++)
        {
            scanf("%d%d %c", &a, &b, &c);
            pos[i].x = a;
            pos[i].y = b;
            pos[i].dir = f(c);
        }
        bad = 0;
        for(i=1; i<=m; i++)
        {
            scanf("%d %c%d", &a, &c, &b);
            if(!bad)
            {
                switch(c)
                {
                case 'F':
                    for(j=1; j<=b; j++) //如果是前进的指令,要走一步看一步
                    {
                        if(pos[a].dir == 1)
                            pos[a].x ++;                    
                        else if(pos[a].dir == 2)
                            pos[a].y --;
                        else if(pos[a].dir == 3)
                            pos[a].x --;
                        else
                            pos[a].y ++;
                        mark[a] = 1;
                        if(k = isexit(pos[a])) //是否有机器人已经在这个位置了
                        {
                            printf("Robot %d crashes into robot %d\n", a, k);
                            bad = 1;
                            break;
                        }
                        mark[a] = 0;
                        if(isout(pos[a])) //是否出界了
                        {
                            printf("Robot %d crashes into the wall\n", a);
                            bad = 1;
                            break;
                        }
                    }
                    break;
                case 'L':
                    for(j=1; j<=b; j++)            //左转b次
                    {
                        pos[a].dir = (pos[a].dir-1) % 4;
                        if(pos[a].dir == 0)
                            pos[a].dir = 4;
                    }
                    break;
            case'R':
                for(j=1; j<=b; j++)                //右转b次
                {
                    pos[a].dir = (pos[a].dir+1) % 4;
                    if(pos[a].dir == 0)
                        pos[a].dir = 4;
                }
                break;
            }
            }
        }
        if(!bad)
            printf("OK\n");
    }
    getch();
    return 0;
}


阅读(1354) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~