Connection Status:
Competition Arena > BuildingRoads

BuildingRoads

SRM 470 · 2009-11-12 · by dolphinigle

SRM 470 · 2009-11-12 · by dolphinigle · Dynamic Programming, Graph Theory
Class Name: BuildingRoads
Return Type: int
Method Name: destroyRocks
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given the map of a country which is divided into a rectangular grid of cells. The country contains several cities, each of which occupies a single cell. Your goal is to connect certain pairs of cities with direct roads. However, there are several large rocks which might get in your way. Each rock potentially spans multiple cells, and costs some amount of money to destroy. You want to build your roads while spending as little money as possible destroying rocks.

You are given the map in the String[] field. The j-th character of the i-th element of field represents the cell at row i, column j. Each cell is one of the following:
  • '.' - Empty space.
  • '!', '@', '#', or '$' - A city. For each of these characters, there can be either 0 or 2 cities denoted by it.
  • 'a'-'z', 'A'-'Z', or '0'-'9' - A cell which is occupied entirely by a rock.
Cells containing rocks which are denoted by the same character are occupied by the same physical rock. Each pair of cells which is occupied by the same rock will be connected. This means that if you label the cells C1 and C2, at least one of the following will be true:
  • C1 and C2 share a side.
  • There exists another cell C3, where C1 and C3 share a side, and C3 is connected to C2.
The character used to denote a rock represents the cost required to destroy that entire rock. The costs are as follows:
  • 'a' - 'z': 1 - 26
  • 'A' - 'Z': 100 - 2,600 (each letter costs 100 more than the previous letter)
  • '1' - '9': 10,000 - 90,000 (each digit costs 10,000 more than the previous digit)
  • '0': 100,000
You must build a road between each pair of cities denoted by the same character. Each road must be a continuous (but not necessarily straight) line which starts in the middle of one city and ends in the middle of the other city. Roads cannot be built outside the boundaries of the map, and roads must not touch any cell which contains a rock (not even the sides or corners of such cells). Return the minimum cost required to destroy all the rocks necessary to build the roads.

Notes

  • The roads are assumed to be arbitrarily thin, and can intersect each other.
  • The roads may pass through any city.

Constraints

  • field will contain between 2 and 50 elements, inclusive.
  • Each element of field will contain between 1 and 50 characters, inclusive.
  • Each element of field will contain the same number of characters.
  • Each character in field will be '.', 'a'-'z', 'A'-'Z', '0'-'9', '!', '@', '#', or '$'.
  • field will contain either zero or two occurrences of '!'.
  • field will contain either zero or two occurrences of '@'.
  • field will contain either zero or two occurrences of '#'.
  • field will contain either zero or two occurrences of '$'.
  • There will be at least two cities in field.
  • Each pair of cells which is occupied by the same rock will be connected (as described in the problem statement).
Examples
0)
{"!1.!",
 "aab2"}
Returns: 3

You must destroy the two rocks which cover the purple cells. The total cost is 3.

1)
{"#@",
 "A.",
 "A1",
 "@#"}
Returns: 100
2)
{"$....",
 "BBBBB",
 "B000B",
 "B0$0B",
 "B000B",
 "BBBBB"}
Returns: 100200
3)
{"$a",
 ".B",
 "$3"}
Returns: 0
4)
{".#!@.$",
 ".11111",
 "..AB..",
 "33AB..",
 "$3AB..",
 "88888a",
 "#!@..."}
Returns: 30301

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

Coding Area

Language: C++17 · define a public class BuildingRoads with a public method int destroyRocks(vector<string> field) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous