hdu 三部曲 Crashing Robots

女爷i 2022-01-05 15:34 305阅读 0赞

Problem Description

In a modernized warehouse, robots are used to fetch the goods. Careful planning is needed to ensure that the robots reach their destinations without crashing into each other. Of course, all warehouses are rectangular, and all robots occupy a circular floor space with a diameter of 1 meter. Assume there are N robots, numbered from 1 through N. You will get to know the position and orientation of each robot, and all the instructions, which are carefully (and mindlessly) followed by the robots. Instructions are processed in the order they come. No two robots move simultaneously; a robot always completes its move before the next one starts moving.  
A robot crashes with a wall if it attempts to move outside the area of the warehouse, and two robots crash with each other if they ever try to occupy the same spot.

Input

The first line of input is K, the number of test cases. Each test case starts with one line consisting of two integers, 1 <= A, B <= 100, giving the size of the warehouse in meters. A is the length in the EW-direction, and B in the NS-direction.  
The second line contains two integers, 1 <= N, M <= 100, denoting the numbers of robots and instructions respectively.  
Then follow N lines with two integers, 1 <= Xi <= A, 1 <= Yi <= B and one letter (N, S, E or W), giving the starting position and direction of each robot, in order from 1 through N. No two robots start at the same position.  
![2632_1.jpg][]  
Figure 1: The starting positions of the robots in the sample warehouse  
Finally there are M lines, giving the instructions in sequential order.  
An instruction has the following format:  
< robot \#> < action> < repeat>  
Where is one of

*  L: turn left 90 degrees,
 *  R: turn right 90 degrees, or
 *  F: move forward one meter,

and 1 <= < repeat> <= 100 is the number of times the robot should perform this single move.

Output

Output one line for each test case:

*  Robot i crashes into the wall, if robot i crashes into a wall. (A robot crashes into a wall if Xi = 0, Xi = A + 1, Yi = 0 or Yi = B + 1.)
 *  Robot i crashes into robot j, if robots i and j crash, and i is the moving robot.
 *  OK, if no crashing occurs.

Only the first crash is to be reported.

Sample Input

4 5 4 2 2 1 1 E 5 4 W 1 F 7 2 F 7 5 4 2 4 1 1 E 5 4 W 1 F 3 2 F 1 1 L 1 1 F 3 5 4 2 2 1 1 E 5 4 W 1 L 96 1 F 2 5 4 2 3 1 1 E 5 4 W 1 F 4 1 L 1 1 F 20

Sample Output

Robot 1 crashes into the wall Robot 1 crashes into robot 2 OK Robot 1 crashes into robot 2

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

大模拟，没技巧，细节很重要。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
      2 #include<string>
      3 #include<cstring>
      4 #include<cstdio>
      5 #include<cctype>
      6 #include<queue>
      7 #include<stack>
      8 using namespace std;
      9 struct node
     10 {
     11     int x,y;
     12     char id;
     13 }robot[1001];
     14 int a,b,n,m,case1,i,j,k;
     15 int mop[1001][1001];
     16 void init()
     17 {
     18     cin>>a>>b>>n>>m;
     19     for(i=1;i<=b;i++)
     20      for(j=1;j<=a;j++)
     21       mop[i][j]=0;
     22     int xx,yy;
     23     char de;
     24     for(i=1;i<=n;i++)//此处反一下
     25      {
     26          cin>>xx>>yy>>de;
     27          //getchar();
     28          robot[i].x=xx;
     29          robot[i].y=b-yy+1;
     30          robot[i].id=de;
     31          //getchar();
     32          mop[b-yy+1][xx]=i;
     33      }
     34 
     35 }
     36 void sovle()
     37 {
     38     init();
     39     int num,times;
     40     char dest;
     41     int cur,k=0;
     42     int flag=1;
     43     while(m--)
     44     {
     45         cin>>num>>dest>>times;
     46        /*getchar();
     47         cin>>dest;
     48         getchar();
     49         cin>>times;
     50         */
     51         if(flag==0)continue;
     52         else
     53         {
     54            cur=num;
     55            for(i=1;i<=times;i++)
     56            {
     57             if(flag==0)break;
     58             if(dest=='F')//直走
     59             {
     60                 if(robot[num].id=='N')
     61                 {
     62                     mop[robot[num].y][robot[num].x]=0;
     63                     robot[num].y--;
     64                     if(robot[num].y<=0)
     65                     {
     66                         flag=0;
     67 
     68                     }
     69 
     70                     else
     71                     {
     72                       if(mop[robot[num].y][robot[num].x]==0)
     73                         mop[robot[num].y][robot[num].x]=num;
     74                       else
     75                       {
     76                           k=mop[robot[num].y][robot[num].x];
     77                           flag=0;
     78                       }
     79                     }
     80                 }
     81                else
     82                 if(robot[num].id=='S')
     83                 {
     84                     mop[robot[num].y][robot[num].x]=0;
     85                     robot[num].y++;
     86                    if(robot[num].y>b)
     87                    {
     88                        flag=0;
     89                        //break;
     90                    }
     91                    else
     92                    {
     93                        if(mop[robot[num].y][robot[num].x]!=0)
     94                        {
     95                            k=mop[robot[num].y][robot[num].x];
     96                            flag=0;
     97                        }
     98                        else
     99                          mop[robot[num].y][robot[num].x]=num;
    100                     }
    101                 }
    102                else
    103                 if(robot[num].id=='E')
    104                 {
    105                     mop[robot[num].y][robot[num].x]=0;
    106                     robot[num].x++;
    107                    if(robot[num].x>a)
    108                    {
    109                        flag=0;
    110                        //break;
    111                    }
    112                    else
    113                    {
    114                        if(mop[robot[num].y][robot[num].x]!=0)
    115                        {
    116                            k=mop[robot[num].y][robot[num].x];
    117                            flag=0;
    118                        }
    119                        else
    120                          mop[robot[num].y][robot[num].x]=num;
    121                     }
    122                 }
    123                 else
    124                  if(robot[num].id=='W')
    125                  {
    126                     mop[robot[num].y][robot[num].x]=0;
    127                     robot[num].x--;
    128                    if(robot[num].x<=0)
    129                    {
    130                        flag=0;
    131                        //break;
    132                    }
    133                    else
    134                    {
    135                        if(mop[robot[num].y][robot[num].x]!=0)
    136                        {
    137                            k=mop[robot[num].y][robot[num].x];
    138                            flag=0;
    139                        }
    140                        else
    141                          mop[robot[num].y][robot[num].x]=num;
    142                     }
    143                 }
    144             }
    145          else
    146            if(dest=='L')//turn left
    147             {
    148                if(robot[num].id=='E')
    149                 robot[num].id='N';
    150                else
    151                 if(robot[num].id=='W')
    152                  robot[num].id='S';
    153                 else
    154                  if(robot[num].id=='N')
    155                  robot[num].id='W';
    156                 else
    157                  if(robot[num].id=='S')
    158                   robot[num].id='E';
    159             }
    160         else
    161            if(dest=='R')//turn right 
    162               {
    163                if(robot[num].id=='E')
    164                 robot[num].id='S';
    165                else
    166                 if(robot[num].id=='W')
    167                  robot[num].id='N';
    168                else
    169                 if(robot[num].id=='N')
    170                  robot[num].id='E';
    171                else
    172                 if(robot[num].id=='S')
    173                  robot[num].id='W';
    174               }
    175         }
    176      }
    177 
    178     }
    179     if(flag==0)
    180     {
    181         if(k==0)
    182          printf("Robot %d crashes into the wall\n",cur);
    183         else
    184          printf("Robot %d crashes into robot %d\n",cur,k);
    185     }
    186     else
    187      printf("OK\n");
    188 }
    189 int main()
    190 {
    191     cin>>case1;
    192     while(case1--)
    193     {
    194       sovle();
    195     }
    196     return 0;
    197 }

坚持！！多刷题！！

转载于:https://www.cnblogs.com/sdau--codeants/p/3351807.html

[2632_1.jpg]: http://acm.hdu.edu.cn/webcontest/images/2632_1.jpg
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/7c7aa2e593ff42ad9ae62618444b19a5.png