SentryBots | Topcoder Archive

Problem Statement

You have studied the castle's defenses. The castle is laid out as a square grid with n corridors going north-south and n going east-west. You are located at one corner of the grid, and can move along the corridors. You must reach the diagonally opposite corner of the castle as quickly as possible. The only problem is the sentry robots.

But you have studied. You know where each bot is currently located and how it will move. Your starting point is x=1, y=1, the southwest corner of the castle. You must reach the point x=n, y=n. You can move at any speed less than or equal to 1 intersection per minute. You can stay stationary at an intersection or in a corridor. You can do a U turn in a corridor. But you cannot pass a robot in a corridor or be at an intersection at the same time that a robot is there.

Each bot travels at a constant speed of 1 (intersection per minute) along a path described by a 4 character string. The first 2 characters are digits giving the initial position x1,y1. The last 2 characters give a position x2,y2, distinct from x1,y1. If the 2 points are on the same corridor, the bot moves back and forth between the 2 points. Otherwise, the bot travels the rectangular path x1,y1 .. x2,y1 ... x2,y2 ... x1,y2 ...x1,y1 ... etc. Bots never interfere with each other -- they can pass each other freely.

The String bots will contain descriptions for each of the bots, separated by a space. Given bots and n, return the minimum time it will take to get to your destination, rounded to the nearest integer. Return -1 if you cannot reach it in less than 1000.5 minutes.

Definition

Class:: SentryBots
Method:: minTime
Parameters:: String, int
Returns:: int
Method signature:: int minTime(String bots, int n)
(be sure your method is public)

Constraints

n will be between 2 and 9, inclusive.
bots will contain between 0 and 49 characters, inclusive.
bots will contain 0 or more bot descriptions, separated by a single space.
Each bot description will consist of exactly 4 digits, each between 1 and n, inclusive.
In each bot description, the points (x1,y1) and (x2,y2) will be distinct.

Examples

```
"1122"
```
```
9
```
```
Returns: -1
```
There is only one bot but it is at the starting intersection.
```
"2211 3122"
```
```
3
```
```
Returns: 4
```
+-----+-----+ | | | +-----+-----+ | A | B | +-----+-----+ There are 2 bots. The first bot is going counterclockwise around the square A, starting at the center of the grid. The other bot is going clockwise around the square B, starting at the lower right corner of the grid. You can't immediately go to either of the intersections adjacent to you since you would run into a bot. An optimal plan is to move almost to the point 2,1, wait for the bot moving around B to pass you and then follow right behind it. When you reach 2,2 you can then continue up to 2,3 and then to 3,3. This will take 4 time units plus an arbitrarily small waiting period.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.