POJ 2632 - Crashing Robots


问题描述

无。

解题思路

简单的模拟题而已。

程序很长不是因为算法(根本就没算法),而是因为很多情况要考虑,要有耐心。

需要小心的是,当坐标系变换后,注意方向的改变规律。

注意事项

  • 坐标系要改变为二维矩阵的形式,N、W、S、E的方向变化必须注意:改变坐标系后,N为南,S为北,WE不变,L转右,R转左,F不变;
  • 对于求余数处理是否注意出现负数的情况;
  • robot移动过程中,crashes robot和crashes wall 同时判断,crashes robot 放在前面。

测试数据

AC 源码

//Memory Time 
//348K   16MS 

#include<iostream>
using namespace std;

int main(void)
{
    int cases;
    int a,b;  //A列数B行数
    int n,m;  //n : robot数, m :  指令数
    int x,y;  //robots坐标
    char dire;  //robots方向
    int rob[101],rep[101];   //rob:编号,rep:指令重复次数
    char act[101];           //act:行动指令

    bool flag=false;
    int i,k;

    int post[101][101];      //记录robot初始方向
    int num[101][101];       //记录robot的编号
    int xx[101],yy[101];     //记录robot的编号

    cin>>cases;
    while(cases--)
    {
        memset(post,-1,sizeof(post));
        memset(num,0,sizeof(num));
        memset(xx,0,sizeof(xx));
        memset(yy,0,sizeof(yy));

        cin>>a>>b;
        cin>>n>>m;

        /*Input the postion and direction of each robot*/
        for(i=1;i<=n;i++)
        {
            cin>>y>>x>>dire;   //使用cin函数时,空字符不会作为字符输入到char
            xx[i]=x;
            yy[i]=y;                  //编号记录(编号作为下标,通过编号反搜坐标)
            num[x][y]=i;              //编号记录(坐标作为下标,通过坐标反搜编号)
            if(dire=='S')             //方向记录(坐标作为下标,通过坐标反搜方向)
                post[x][y]=0;        //0 or 360     【由于坐标系改变,注意上下颠倒,即N为南,S为北,但WE不变】
            else if(dire=='E')
                post[x][y]=1;        //90
            else if(dire=='N')
                post[x][y]=2;        //180
            else if(dire=='W')
                post[x][y]=3;        //270
        }                            //用0~3代替是为了减少运算次数

        /*Input < robot #> < action> < repeat>*/
        for(k=1;k<=m;k++)
            cin>>rob[k]>>act[k]>>rep[k];

        bool flag=false;
        int row,col;
        for(k=1;k<=m;k++)
        {
            row=xx[rob[k]];
            col=yy[rob[k]];

            if(act[k]=='L')       //【由于坐标系改变,注意转向相反:L转右,R转左】
            {
                rep[k]%=4;   //角度每转4次(360度)回到原位
                post[row][col] = ( post[row][col] + rep[k] ) % 4;
            }
            else if(act[k]=='R')
            {
                rep[k]%=4;
                post[row][col] = ( post[row][col] - rep[k] ) % 4;
                if(post[row][col]<0)   //注意余数为负的情况
                    post[row][col]+=4;
            }
            else if(act[k]=='F')
            {
                if(post[row][col]==0)      //N方向移动判断
                    for(i=1;i<=rep[k];i++)
                    {
                        if(num[row-i][col]) //如果该格存在编号(即存在另外的robot)
                        {
                            cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row-i][col]<<endl;
                            flag=true;
                            break;
                        }
                        if(row-i<1)  //判断是否撞墙
                        {
                            cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;
                            flag=true;
                            break;
                        }
                        if(i==rep[k])
                        {   //移动中若无任何碰撞,则把robot原坐标记录的信息更新到新坐标
                            post[row][col]=-1;   //原坐标方向重置
                            num[row][col]=0;      //原坐标编号重置
                            row-=rep[k];
                            xx[rob[k]]-=rep[k];
                            post[row][col]=0;    //新坐标方向更新
                            num[row][col]=rob[k];   //新坐标编号更新
                        }
                    }
                else if(post[row][col]==1)  //E方向移动判断
                    for(i=1;i<=rep[k];i++)
                    {
                        if(num[row][col+i])
                        {
                            cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row][col+i]<<endl;
                            flag=true;
                            break;
                        }
                        if(col+i>a)
                        {
                            cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;
                            flag=true;
                            break;
                        }
                        if(i==rep[k])
                        {
                            post[row][col]=-1;
                            num[row][col]=0;
                            col+=rep[k];
                            yy[rob[k]]+=rep[k];
                            post[row][col]=1;
                            num[row][col]=rob[k];
                        }
                    }
                else if(post[row][col]==2)  //S方向移动判断
                    for(i=1;i<=rep[k];i++)
                    {
                        if(num[row+i][col])
                        {
                            cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row+i][col]<<endl;
                            flag=true;
                            break;
                        }
                        if(row+i>b)
                        {
                            cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;
                            flag=true;
                            break;
                        }
                        if(i==rep[k])
                        {
                            post[row][col]=-1;
                            num[row][col]=0;
                            row+=rep[k];
                            xx[rob[k]]+=rep[k];
                            post[row][col]=2;
                            num[row][col]=rob[k];
                        }
                    }
                else if(post[row][col]==3)  //W方向移动判断
                    for(i=1;i<=rep[k];i++)
                    {
                        if(num[row][col-i])
                        {
                            cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row][col-i]<<endl;
                            flag=true;
                            break;
                        }
                        if(col-i<1)
                        {
                            cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;
                            flag=true;
                            break;
                        }
                        if(i==rep[k])
                        {
                            post[row][col]=-1;
                            num[row][col]=0;
                            col-=rep[k];
                            yy[rob[k]]-=rep[k];
                            post[row][col]=3;
                            num[row][col]=rob[k];
                        }
                    }
            }
            if(flag)break;
        }
        if(!flag)
            cout<<"OK"<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1472 - Instant Complexity POJ 1472 - Instant Complexity
POJ 1472 - Instant Complexity Time: 1000MS Memory: 10000K 难度: 中级 分类: 模拟法 问题描述给出一段Pascial程序,计算其时间复杂度(能计算的项则计算,不能计算则化到最简
2011-09-14
下一篇 
POJ 2533 - Longest Ordered Subsequence POJ 2533 - Longest Ordered Subsequence
POJ 2533 - Longest Ordered Subsequence Time: 2000MS Memory: 65536K 难度: 初级 分类: 动态规划 问题描述无。 解题思路动态规划,求LIS最大不下降子序列 O(n^2)
2011-09-13
  目录