Connection Status:
Competition Arena > TwoRobots

TwoRobots

SRM 792 · 2020-10-21 · by misof

SRM 792 · 2020-10-21 · by misof · Graph Theory
Class Name: TwoRobots
Return Type: int
Method Name: move
Arg Types: (vector<string>)
Problem Statement

Problem Statement

There is a factory. The floor of the factory is a rectangle divided into unit squares. Some unit squares are walls, others are empty. You are given the plan of the factory: a String[] in which each '#' represents a wall and each '.' an empty square.

There are two robots in the factory: robot A and robot B. Their current locations are denoted 'A' and 'B' in the plan.

Both robots move synchronously at one step per second. In each step the robot must move from its current square to one of the squares that share a side with its current square. The robots cannot leave the factory, they cannot move to a wall, they cannot both move to the same square, and they also cannot trade spaces.

Robot A wants to reach location marked 'a' in the plan, and robot B wants to reach location marked 'b' at the same time. (The starting locations of both robots and their destinations also count as empty squares. The robots may enter them arbitrarily many times.)

Compute and return the minimum time in which both robots can reach their desired destinations at the same time. If that is impossible, return -1 instead.

Constraints

  • plan will contain between 1 and 40 elements, inclusive.
  • Each element of plan will contain between 1 and 40 characters, inclusive.
  • Each element of plan will contain the same number of characters.
  • plan will contain exactly one 'A', exactly one 'B', exactly one 'a', and exactly one 'b'.
  • Each other character in plan will be either '#' or '.'.
Examples
0)
{"Ab.a",
 "...B"}
Returns: 3

Robot A will make three steps right while robot B will step left, left, and up.

1)
{"#a#",
 "A.b",
 "#B#"}
Returns: -1

The two robots are unable to take the very first step: each of them has to go into the middle, but they cannot both go to the same square.

2)
{"#b#",
 "A.a",
 "#B#",
 "#.#"}
Returns: -1

Still no solution. Now robot B can start by going down, but there is no way to reach the two destination cells at the same time: one second before that happens they would both need to be in the same empty square.

3)
{"...",
 "#a#",
 "A.b",
 "#B#",
 "#.#"}
Returns: 4

A can go right, up, up, down while B goes down, up, up, right.

4)
{"AB......ab"}
Returns: 8

Both robots simply go right. Note that one robot may enter a cell the other robot left during the same second.

5)
{"bA......Ba"}
Returns: -1

The robots cannot swap spaces, so on this map they can never reach their goals.

6)
{"bA.......Ba"}
Returns: -1

This example is one square longer than the previous one. Again, robot A cannot move past robot B. On this map, this would involve both of them stepping onto the same square at some moment.

7)
{"AB.........",
 "...........",
 "...........",
 "........b.a"}
Returns: -1

Plenty of room for maneuvers, but it's still impossible for the robots to reach 'a' and 'b' at the same time.

8)
{"...A...",
 ".#####.",
 ".#####b",
 "B#####.",
 ".#####.",
 ".#####.",
 "..a...."}
Returns: 13

The two robots must essentially go around the walls in the same direction. (If each robot selfishly tries to follow the shortest path to their destination, they will collide in the top left corner.)

Submissions are judged against all 114 archived test cases, of which 9 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TwoRobots with a public method int move(vector<string> plan) · 114 test cases · 2 s / 256 MB per case

Submitting as anonymous