POJ-2632-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

POJ-2632

简介: #include 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...

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


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章