Connection Status:
Competition Arena > PizzaDelivery

PizzaDelivery

SRM 451 · 2009-10-20 · by vexorian

SRM 451 · 2009-10-20 · by vexorian · Brute Force, Graph Theory
Class Name: PizzaDelivery
Return Type: int
Method Name: deliverAll
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Tom McCoffee owns the only pizza delivery place in the mountains. The terrain is represented as a rectangular grid of squares, where each square either contains a building or is empty. Each empty square has an integer height between 0 and 9, inclusive. Today, each building in the area has ordered one pizza, and Tom must use his two delivery boys to fulfill all the orders in the shortest total amount of time possible.

From each square in the grid, you can only move to adjacent squares. Two squares are adjacent if they share an edge. You can only move between two empty squares if the absolute difference of their heights is less than or equal to 1. If the height difference is 0, it takes 1 minute to make the move, and if the absolute height difference is 1, it takes 3 minutes.

You can always move to a building from any of its adjacent squares and vice versa, regardless of height. This is because all buildings are taller than the highest terrain, and each building has entrances and exits for all its adjacent squares at the correct heights. Moving to or from a square containing a building takes 2 minutes. The delivery boys are allowed to enter buildings even if they are not their final destinations. Note that the pizza place itself is also a building.

Each delivery boy can only carry one pizza at a time. This means that after each delivery, the delivery boy must return to the pizza place to pick up another pizza if there are more deliveries left to do. You are given a String[] terrain, where the j-th character of the i-th element represents the square at row i, column j of the terrain. '$' represents a building from which a pizza was ordered, 'X' represents the location of the restaurant, and the digits '0'-'9' represent the heights of empty squares. The initial time is 0. Return the minimum time in minutes at which the last delivery can be made. If it is not possible to deliver all the pizzas, return -1 instead.

Constraints

  • terrain will contain between 2 and 50 elements, inclusive.
  • Each element of terrain will contain between 2 and 50 characters, inclusive.
  • Each element of terrain will contain the same number of characters.
  • Each character in terrain will be 'X', '$' or a digit between '0' and '9', inclusive.
  • terrain will contain between 1 and 20 '$' characters, inclusive.
  • terrain will contain exactly one 'X' character.
Examples
0)
{"3442211",
 "34$221X",
 "3442211"}
Returns: 8

Only one pizza boy is needed for this single delivery. The pizza boy must first take two minutes to go from the restaurant to the cell to its left. Then he must climb from the cell of height '1' to the left cell of height '2' , taking 3 minutes. The movement between two cells of height '2' takes one minute. He finally needs two more minutes to go from the cell of height '2' to the only building in the area.

1)
{"001000$",
 "$010X0$",
 "0010000"}
Returns: 13

This time there are three buildings, and an optimal solution is as follows: 00:00 -> Pizza boy #1 takes the pizza assigned for the left building. 00:00 -> Pizza boy #2 takes the pizza assigned for the right building. 00:04 -> Pizza boy #2 delivers the pizza to the right building. 00:08 -> Pizza boy #2 arrives back at the restaurant, takes the pizza for the top-right building. 00:10 -> Pizza boy #1 delivers the pizza to the left building. 00:13 -> Pizza boy #2 delivers the pizza to the top-right building.

2)
{"001000$",
 "$010X0$",
 "0010000",
 "2232222",
 "2222222",
 "111$111"}
Returns: -1

The irregular terrain blocks deliveries to the bottom building.

3)
{"001000$",
 "$010X0$",
 "0010000",
 "1232222",
 "2222222",
 "111$111"}
Returns: 28

This time, there is a possible path connecting the restaurant and the bottom building.

4)
{"X$$",
 "$$$"}
Returns: 14

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

Coding Area

Language: C++17 · define a public class PizzaDelivery with a public method int deliverAll(vector<string> terrain) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous